2636 : 치즈 (C++)

2636번: 치즈

---

치즈문제!

BFS로 풀었다

먼저 BFS탐색을 통해 공기로 차있는 부분들을 방문표시한다.

정사각형 칸의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다고 했으므로

항상 map[0][0]부분은 공기 부분이므로 queue에 0,0을 넣고 공기인 부분을

탐색한 후 치즈를 녹인다. 치즈가 모두 남아있지 않을 때까지 계속 수행한다.

또한 치즈가 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여있는 칸의 수를 구하라 했으므로

치즈를 녹이기 전 항상 치즈조각이 남아있는 갯수를 세준 후 탐색을 진행한다.

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int N, M;
int hours;
int counting;
int minimum = 0;

int map[100][100];
bool visit[100][100];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

queue<pair<int, int>> q;

void airBfs() {
    int x = q.front().first;
    int y = q.front().second;
    visit[x][y] = true;

    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if(map[nx][ny] == 0 && visit[nx][ny] == false) {
                    q.push({nx, ny});
                    visit[nx][ny] = true;
                }
            }

        }
    }
}

void meltingCheese() {
    for(int x = 0; x < N; x++) {
        for(int y = 0; y < M; y++) {
            if(map[x][y] == 1) {
                for(int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if(map[nx][ny] == 0 && visit[nx][ny] == true && map[x][y] == 1) {
                        // 공기층일때
                        map[x][y]--;
                        // 녹이고
                        break;
                        // 반복문 탈출
                    }
                }
            }
        }
    }
}

int main() {
    cin >> N >> M;

    // 치즈 입력
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }

    while(true) {
        counting = 0;

        for(int x = 0; x < N; x++) {
            for(int y = 0; y < M; y++) {
                if(map[x][y] == 1) {
                    counting++;
                }
            }
        }

        if(counting == 0) {
            break;
        } else {
            minimum = counting;
        }

        memset(visit, false, sizeof(visit));
        // visit 배열 초기화

        q.push({0, 0});
        // map[0][0]은 항상 0이므로 공기가 들어가지 않은 구멍층과 구분가능

        airBfs();
        // 공기인 부분 탐색

        meltingCheese();
        // 치즈 녹이기

        hours++;

    }

    cout << hours << "\n" << minimum << "\n";

    return 0;
}