문제
풀이
문제의 핵심은 외부 공기와 내부 공기를 구분하는 것이다. 이는 BFS를 활용하여 구현할 수 있다.
- 알고리즘
- 모눈종이의 테두리는 항상 비어있기 때문에 (0, 0)에서 시작하여 bfs로 탐색해준다. 1(치즈)인 부분은 막혀있다고 가정하면 bfs로 갈 수 있는 부분이 외부공기이다. 외부공기는 2로 치환해준다.
- 주변에 접해있는 바깥공기의 개수를 저장해주는 outAir라는 2차원 배열을 선언한다. 1번에서 bfs로 탐색하면서 카운트해준다. 자세한 코드는 아래에서 살펴보자.
- outAir 가 2 이상인 좌표는 녹는 부분이므로 0으로 치환해준다.
- 1,2,3 단계를 녹는 치즈가 없을 때 까지 while문으로 반복한다. 반복할 때 마다 outAir 배열과 방문확인용 visit 배열을 초기화해주는 것을 잊지말자.
소스 코드
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <queue>
#include <iostream>
#include <cstring>
using namespace std;
struct pos
{
int y, x;
};
int paper[101][101];
bool visit[101][101]; //방문 확인
int outAir[101][101]; // 주변 바깥공기개수 카운트
int n, m;
int dy[] = {0, 1, 0, -1};
int dx[] = {-1, 0, 1, 0};
// input 함수
void input()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> paper[i][j];
}
}
}
// 바깥공기를 2로 할당해주는 과정, BFS사용
void spreadAir()
{
queue<pos> q;
q.push({0, 0});
while (!q.empty())
{
pos cur = q.front();
int y = cur.y;
int x = cur.x;
q.pop();
if (visit[y][x])
continue;
visit[y][x] = true;
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= n || nx >= m)
continue;
// 현재 좌표가 바깥공기이므로 다음좌표는 바깥공기와 닿아있는것
if (paper[ny][nx] == 1)
outAir[ny][nx]++;
else if (!visit[ny][nx])
q.push({ny, nx});
}
}
}
// 녹는 치즈를 0으로 치환하는 과정
bool melt()
{
bool isMelted = false;
for (int i = 1; i < n - 1; i++)
{
for (int j = 1; j < m - 1; j++)
{
if (outAir[i][j] >= 2)
{
paper[i][j] = 0;
isMelted = true;
}
}
}
return isMelted;
}
void solve()
{
int t = 0;
while (true)
{
// visit, outAir 초기화
memset(visit, 0, sizeof(visit));
memset(outAir, 0, sizeof(outAir));
spreadAir();
bool isMelted = melt();
if (isMelted)
t++;
// 아무것도 녹지 않았다면 break
else
break;
}
cout << t << '\n';
}
int main()
{
input();
solve();
return 0;
}
