https://www.acmicpc.net/problem/2636
2636번: 치즈
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓
www.acmicpc.net
문제 이해
1. 공기(0) 옆에 있는 치즈(1)를 녹인다 (= 공기로 바꾼다)
2. 단, 치즈로 둘러쌓인 공간은 공기지만 치즈를 녹이지 않는다.
3. 문제의 핵심은 벽면은 모두 공기라는 것이다. 즉 (0, 0)에서 출발하면 치즈 내 구멍을 뺀 바깥 공기 모두를 탐색할 수 있다.
해결: 치즈가 모두 녹을 때까지 BFS를 실행한다.
작성 코드 (C)
#include <stdio.h>
int Y, X;
int map[100 + 5][100 + 5];
int cnt; // 남은 치즈의 개수
int time; // 지난 시간
int left; // 마지막 남은 치즈 개수
// 방향 벡터
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
// 큐
typedef struct POS {
int y;
int x;
}POS;
POS q[100 * 100 + 10];
int rp, wp;
void enq(int y, int x) {
q[wp].y = y;
q[wp].x = x;
wp++;
}
POS deq() {
POS tmp = q[rp];
rp++;
return tmp;
}
int empty() {
return wp == rp;
}
void bfs(int y, int x) {
int visited[100 + 5][100 + 5] = {0,};
wp = 0, rp = 0;
visited[y][x] = 1;
enq(y, x);
while (!empty()) {
POS cur = deq();
for (int i = 0; i < 4; i++) {
int ny = dy[i] + cur.y;
int nx = dx[i] + cur.x;
if (ny < 0 || ny >= Y) continue;
if (nx < 0 || nx >= X) continue;
if (visited[ny][nx] == 1) continue;
visited[ny][nx] = 1;
// 만약 공기이면
if (map[ny][nx] == 0) {
enq(ny, nx);
}
// 만약 치즈라면 녹이고, 큐에 넣지 않음
if (map[ny][nx] == 1) {
map[ny][nx] = 0;
cnt--;
}
}
}
time++;
}
int main(void) {
// 입력받기
scanf("%d %d", &Y, &X);
for (int i = 0; i < Y; i++) {
for (int j = 0; j < X; j++) {
scanf("%d", &map[i][j]);
if (map[i][j] == 1) cnt++;
}
}
// (0, 0)에서 시작
while (cnt > 0) {
left = cnt;
bfs(0, 0);
}
printf("%d\n%d", time, left);
return 0;
}
'컴퓨터기본 > 문제풀이' 카테고리의 다른 글
[백준] 2479번: 경로 찾기 (0) | 2021.09.24 |
---|---|
[백준] 2564번: 경비원 (0) | 2021.09.23 |
[백준] 1193번: 분수찾기 (0) | 2021.09.18 |
[백준] 2775번: 부녀회장이 될테야 (0) | 2021.09.18 |
[백준] 2292번: 벌집 (0) | 2021.09.18 |