[BaekJoon] 2638 치즈 :: monton

문제

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

풀이

가중치 없는 최소 거리를 구하는 것이므로 bfs로 사용

외부에 닿아있는 치즈를 구할때는 dfs 사용

내부에 있는 공기는 신경 쓰지 않기 때문에 이 부분은 (0,0)에서 dfs를 시작하면 만나는 1만 queue에 넣어준다 (visit으로 체크)

그러면 외부에 공기만 닿아있는 치즈만 담을 수 있다.

큐에 들어가있는 좌표의 치즈가 외부 공기에 2면 이상 맞닿아있는지 확인해야 되는데

visit이 1이면서 0인 값이 상하좌우로 있나 확인하면 된다

코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, M,ans;
int arr[101][101];
int visit[101][101];
int makezro[101][101];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
queue <int> qx, qy;
 
void chkch(int x, int y) {
    if (x < 0 || x >= N || y < 0 || y >= M) return;
    if (visit[x][y]) return;
    visit[x][y] = 1;
 
    if (arr[x][y]) {
        qx.push(x), qy.push(y);
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        chkch(x + dir[i][0], y + dir[i][1]);
    }
}
 
int chkzero() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j]) return 1;
        }
    }
    return 0;
}
 
void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visit[i][j] = 0;
        }
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
 
    while (chkzero()) {
        init();
        chkch(0, 0);
 
        while (!qx.empty()) {
            int x = qx.front();
            int y = qy.front();
            
            qx.pop(), qy.pop();
            int num = 0;
            if (x - 1 >= 0 && visit[x-1][y]&&!arr[x - 1][y]) num++;
            if (x + 1 <=N && visit[x + 1][y] && !arr[x + 1][y]) num++;
            if (y - 1 >= 0 && visit[x][y-1] && !arr[x][y-1]) num++;
            if (y + 1 <=M && visit[x][y+1] && !arr[x][y+1]) num++;
            if (num > 1) makezro[x][y] = 1;
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (makezro[i][j]) arr[i][j] = 0;
            }
        }
 
        ans++;
    }
    cout << ans;
}