https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.
www.acmicpc.net
|
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
|
#include<stdio.h>
#include<string.h>
#define NSIZE 100
using namespace std;
int N, M;
int input[NSIZE][NSIZE];
int chk[NSIZE][NSIZE];
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
int flag = 0;
void dfs(int y, int x,int cnt) {
for (int dir = 0; dir < 4; dir++) {
int ny = y + dy[dir]; int nx = x + dx[dir];
if (0 <= ny && ny < N && 0 <= nx && nx < M) {
if (input[ny][nx] == 0 && chk[ny][nx] == 0) {
chk[ny][nx] = cnt;
dfs(ny, nx, cnt);
}
}
}
}
void init() {
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &input[i][j]);
}
}
}
void chkair() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (input[i][j] == 1) {
int cnt = 0;
for (int dir = 0; dir < 4; dir++) {
int ny = i + dy[dir];
int nx = j + dx[dir];
if (chk[ny][nx] == 1) cnt++;
}
if (cnt >= 2) {
flag = 1;
input[i][j] = 0;
}
}
}
}
}
int main(void) {
int time = 0;
init();
while (1) {
flag = 0;
memset(chk, 0, sizeof(chk));
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (input[i][j] == 0 && chk[i][j] == 0) {
chk[i][j] =++cnt;
dfs(i, j, cnt);
}
}
}
chkair();
if (flag == 0)break;
time++;
}
printf("%d\n",time);
return 0;
}
|
치즈 문제는 정말 단순하게 생각하시면 금방 푸는데 이걸 가장 어려워하는 것이 안 공기와 바깥 공기를 어떻게 구별
할 것인가입니다. 근데 지금까지 배워왔던 것을 잘 생각해보면 이미 해본 것입니다. 그림을 그려 설명드리자면
그림을 보시니 감이 오시나요? 지금까지 한두번 접해 보았던 플러드 필로 안공기 바깥공기를 나눌 수 있습니다.
무슨 말이냐 하면0,0 부터 0인 부분에서 dfs로 플러드 필을 한다면 가장 처음 만나는 0 즉 공기는 전부 바깥공기가 되는 것이고 그 이외는 치즈 안에 있는 안공기가 되는 것입니다. 이렇게 할 수 있는 것이
문제를 잘 읽어보면 가장자리는 무조건 공기임으로 0,0 인경우 인접하는 배열은 안 공기이므로 저렇게 체크를 해놓고
치즈가 1인 부분가 2개 이상이라면 그 치즈를 녹이면 되는 것입니다.
말로 설명하니 좀 이해가 안되게 설명한 것 같기도 하고 그렇네요 방법은 플러드 필을 이용해라입니다.
그렇게 해서 2 이상인 공기와 접촉했다하면 치즈를 0으로 바꾸면되는데 2이상인 치즈가 없다 하면 break를 걸어
나오면 되는 것입니다.
오늘도 여기까지 이면 즐거운 알고리즘 하세요.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 16918 봄버맨 (0) | 2019.09.17 |
|---|---|
| 백준 9019 DSLR (0) | 2019.09.17 |
| 백준 1726 로봇 (0) | 2019.09.17 |
| 백준 2468 안전영역 (0) | 2019.09.17 |
| 백준 1938 통나무 옮기기 (0) | 2019.09.11 |
댓글