반응형
'치즈' 라는 이름을 가진 문제가 2개 있다. 두 문제는 다른 문제이다.
링크에 들어가서 2638 '치즈' 문제의 설명을 보고 오자.
기존의 2636 '치즈' 의 문제랑 상당히 유사하다. 하지만 다른 점이 있다면, 치즈의 2면 이상이 공기랑 접촉해 있을 때, 치즈가 사라진다는 조건이다.
치즈가 2면 이상 공기랑 접촉해 있는 것을 어떻게 알 수 있을까? 답은 2번 방문했을 경우를 예외로 두면 된다. 2번 방문했다는 것은 공기를 기준으로 bfs를 돌렸을 때, 최소 2면이 공기랑 닿아 있다는 얘기이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef struct
{
int x;
int y;
} loc;
int map[101][101];
int visited[101][101];
loc moves[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int M, N, now_cheeze = 0, last_cheeze = 0, time = 0;
void bfs()
{
queue<loc> q;
memset(visited, 0, sizeof(visited));
visited[0][0] = 1;
q.push({0, 0});
while (!q.empty())
{
loc start = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
loc next = {start.x + moves[i].x, start.y + moves[i].y};
/* 인덱스 벗어나지 않는지 */
if (next.x >= 0 && next.x < M && next.y >= 0 && next.y < N)
{
/* 치즈가 없을 경우 */
if (map[next.x][next.y] == 0)
{
/* 방문하지 않았을 경우 */
if (!visited[next.x][next.y])
{
visited[next.x][next.y]++;
q.push({next.x, next.y});
}
}
/* 치즈가 있을 경우 */
else
{
/* 1회 이하 방문했을 경우 */
if (!visited[next.x][next.y])
visited[next.x][next.y]++;
else
{
map[next.x][next.y] = 0;
now_cheeze--;
}
}
}
}
}
time++;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> M >> N;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
cin >> map[i][j];
if (map[i][j] == 1)
now_cheeze++;
}
}
while (now_cheeze)
{
last_cheeze = now_cheeze;
bfs();
}
cout << time << "\n";
return (0);
}
|
cs |
반응형
'개발 지식 > 알고리즘' 카테고리의 다른 글
[백준] 1325 효율적인 해킹 (0) | 2021.05.08 |
---|---|
[백준] 1074 Z (0) | 2021.04.30 |
[백준] 2636 치즈 (0) | 2021.04.24 |
[백준] 1915 가장 큰 정사각형 (0) | 2021.04.17 |
[백준] 5567 결혼식 (0) | 2021.04.11 |