BOJ 2638 : 치즈

풀이요약

BFS

풀이상세

1. 공기 면적을 탐색하는 중, 치즈를 발견한다면 치즈(1) 값을 한 칸씩 올리는 방식으로 진행했다.
2. 완탐을 하는 도중 치즈(3) 을 만난다면 그 치즈는 공기가 2변 이상 접촉하는 것이 된다.
3. 이러한 방식으로 진행하는 경우 조심할 점이 3가지 있다.
   • 치즈가 한 면적에만 닿아 2가 된 체 완탐이 끝나는 경우가 있다. 다음 완탐으로 진행하기 전, 2로 끝난 치즈를 다시 1로 초기화한다.
   • 2변 이상 닿아야 한다는 것은 치즈가 1 혹은 2의 상태에서는 아직 방문처리를 해서는 안된다는 것이다.
   • 임의의 치즈가 3이 되었다면 해당 치즈는 녹은 것이므로 다음 완탐을 위해 공기 면적으로 바꿔줘야 한다. 단, 이번 완탐에서는 더 이어지면 안되기 때문에, 이 경우는 방문처리를 해준다.

배운점

• 뭔가 3차원 배열로도 가능할 거 같긴하다. 아니면 방문처리를 true, false 가 아닌 int[][] 배열로 하는 게 더 나았을 거 같다.
• 코드 내부에 배열을 만드는 경우, C++은 초기화가 안되나보다. fill 을 활용하는 방법도 있으나 memset을 활용해도 괜찮은 듯 하다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> pi;
int N, M, arr[104][104], cnt, c_cnt, dr[4] = {-1, 0, 1, 0}, dc[4] = {0, -1, 0, 1};
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) c_cnt++;
        }
    }
}

void solve() {
    bool visited[N][M];
    memset(visited, false, sizeof (visited));
    queue<pi> q;
    q.push({0, 0});
    visited[0][0] = true;
    while (!q.empty()) {
        pi curr = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = curr.first + dr[d];
            int nc = curr.second + dc[d];
            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            if (visited[nr][nc]) continue;
            if(arr[nr][nc] == 0 || arr[nc][nc] >= 3) {
                visited[nr][nc] = true;
            } else if(arr[nr][nc] >=1) {
                arr[nr][nc]++;
                if(arr[nr][nc] == 3) {
                    arr[nr][nc] = 0;
                    c_cnt--;
                    visited[nr][nc] = true;
                }
                continue;
            }
            q.push({nr,nc});
        }
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(arr[i][j]==2) arr[i][j] = 1;
        }
    }
}

void output() {
    cout << cnt;
}

int main() {
    input();
    while (c_cnt != 0) {
        cnt++;
        solve();
    }
    output();
}