[백준] 2638 - 치즈
[링크] https://www.acmicpc.net/problem/2638
💎 문제 조건과 설명
문제 조건과 설명은 위의 링크를 참조 부탁드립니다.
🧀 생각한 아이디어
이 문제는 치즈 내부의 빈 칸들을 치즈 외부의 빈 칸들과 어떻게 구분해 놓느냐 하는 것이 중요합니다.
만약에 이 문제가 치즈 내, 외부라는 구분이 없이 모두 동일한 빈 칸들이었다면, 단순히 모든 치즈 칸들에 대해 상,하,좌,우 칸들을 검사하고 2칸 이상이 빈 칸이라면 그 치즈칸을 녹게 하면 끝납니다.
그러나 이 문제는 치즈 내부는 치즈 외부 공기와는 다른 것으로 취급합니다.
따라서 이것을 구분만 시켜놓으면, 그 외의 풀이 과정은 위에서 말한 그대로 하면 됩니다.
치즈 내, 외부 빈칸을 구분시키는 방법은 BFS를 활용합니다. 시작 칸은 (0, 0)을 큐에 넣고 출발하면 됩니다.
모든 칸들에 대해서 상, 하, 좌, 우 칸들을 살펴보고, 빈 칸이었다면 큐에 넣고, 그 칸은 외부 공기라는 표시를 해놓으며 BFS를 진행합니다. 단, 살펴본 칸이 치즈인 칸(=1)이었을 경우 그 칸은 큐에 넣지 않습니다.
즉, 치즈인 칸(=1) 안으로는 BFS를 진행하지 않으므로 내부의 빈 칸은 방문하지 않습니다.
외부 공기라는 표시를 예를 들어 3으로 표시했다면, BFS를 모두 진행한 뒤에는 아래처럼 구분될 것입니다.
- 구분 전
1
2
3
4
5
6
7
8
9
8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0
- 구분 후
1
2
3
4
5
6
7
8
9
8 9
3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3
3 1 1 3 3 3 1 1 3
3 1 0 1 1 1 0 1 3
3 1 0 0 1 0 0 1 3
3 1 0 1 1 1 0 1 3
3 1 1 3 3 3 1 1 3
3 3 3 3 3 3 3 3 3
이제 이렇게 구분된 땅을 가지고, 치즈인 칸들만 살펴 봅니다.
치즈인 칸을 기준으로 상, 하, 좌, 우 중 적어도 두 군데가 외부 공기(=3) 이었을 경우, 그 치즈 칸은 녹을 대상이라고 표기해 둡니다. (별도로 5라고 표기해 두었습니다.)
녹는 대상을 모두 표기했다면, 그 칸들을 전부 외부 공기(=3)로 바꾸어 줍니다.
그런 다음 다시 외부, 내부 공기를 구분하는 과정을 거치고, 치즈를 녹여 줍니다. 과정의 반복입니다.
과정을 단순화하면 다음과 같습니다.
(1) 치즈 내, 외부 공기 구분하기(
BFS)(2) 모든 치즈 칸을 살펴보는데 치즈의 상,하,좌,우 중 적어도 2군데 이상이 바깥 공기인지 확인하고 맞다면 그 치즈를 녹을 대상으로 표기하기
(3) 녹을 대상으로 표기된 치즈들을 전부 외부 공기로 바꾸어 주기
(4) (1) .. 반복
이 때, (3)번 과정이 끝나고, 치즈가 남아있는지 확인하는 별도의 검사를 추가하면 됩니다.
🧀 소스코드(C++)
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
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define REAL_BLANK 3
#define CHEESE 1
#define BLANK 0
#define MELT 5
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int N, M, time;
int arr[101][101];
int visit[101][101];
// 치즈 내, 외부 구분하는 함수
void fill_blank() {
// visit 초기화
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visit[i][j] = 0;
}
}
queue<pair<int, int>>q;
q.push({ 0,0 });
visit[0][0] = 1;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ty = y + dy[i];
int tx = x + dx[i];
if (ty >= 0 && tx >= 0 && ty < N && tx < M &&
visit[ty][tx] == 0 && arr[ty][tx] != CHEESE) {
visit[ty][tx] = 1;
arr[ty][tx] = REAL_BLANK;
q.push({ ty,tx });
}
}
}
}
void simulation() {
bool flag = false;
// 모든 칸을 다 살펴본다.
while (1) {
// (1) 치즈 내, 외부 구분시키기
fill_blank();
// (2) 모든 치즈 칸들을 대상으로 녹을 수 있는지 확인하기
flag = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 해당 칸이 치즈일 경우
if (arr[i][j] == CHEESE) {
int cnt = 0;
// 그 칸의 상,하,좌,우를 살펴보고 최소 2칸이 REAL_BLANK인지 확인
for (int k = 0; k < 4; k++) {
int ty = i + dy[k];
int tx = j + dx[k];
if (ty >= 0 && tx >= 0 && ty < N && tx < M &&
arr[ty][tx] == REAL_BLANK) {
flag = true;
cnt++;
}
}
if (cnt >= 2) arr[i][j] = MELT; // 녹는 대상으로 표기
}
}
}
// (3) 녹는 대상으로 표기된 적이 있을 경우 외부 공기로 바꾸기
if (flag) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] == MELT) {
arr[i][j] = REAL_BLANK;
}
}
}
}
time++;
flag = false;
// 치즈가 남아있는지 재검사
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] == CHEESE) {
flag = true;
}
}
}
if (!flag) break;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> arr[i][j];
}
}
simulation();
cout << time;
return 0;
}