[백준] 2636번: 치즈

https://www.acmicpc.net/problem/2636

2636번: 치즈

문제 이해

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;
}