[2636번][C/C++] 치즈

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

2636번: 치즈

 

공기구멍이 송송 뚫려있는 치즈가 있을 때, 바깥공기와 닿은 치즈 부분이 한 층씩 녹아내리는 상황을 시뮬레이션하는 문제이다.

 

일단 2차원 맵에서 탐색을 해야한다는 것을 봤을 때 직관적으로 BFS가 생각난다.

아니나 다를까 이 문제는 BFS를 사용해서 한 층씩 치즈의 겉을 녹여라! 라는 문제이다.

 

문제에서는 친절하게 맵의 가장자리는 무조건 공기로 채워져 있다는 제약조건을 준다.

만약 가장자리까지 치즈가 있을 수 있었다면 조금은 더 생각해 볼 점이 있을 문제였을 것이다.

하지만 이 문제의 조건을 이용하면 간단해진다.

0번 행,열을 사용하지 않는다고 했을 때, 매번 (1, 1)에서 BFS로 치즈를 녹여주면 된다.

 

녹이는 건 위와 같이 간단하게 끝냈다.

그런데 하나 더 생각해야 할 점이 있다.

치즈가 아예 사라지기 전에 마지막으로 남은 치즈의 개수를 출력해야 한다는 조건이다.

이 조건은 meltdown함수가 매 번 자기가 녹인 치즈의 수를 리턴하게 만들고, while문을 이용해서 해결했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

#define INF 1987654321

using namespace std;

int N, M, curStage = 1;
int direc[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int map[102][102];
int visited[102][102];

bool isIn(int y, int x) {
    if(0<y && y<=N && 0<x && x<=M) return true;
    else return false;
}

int meltdown(int sY, int sX, int stage) {
    queue<pair<int, int>> q;
    int cnt = 0;
    q.push({sY, sX});
    visited[sY][sX] = stage;

    while(!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        if(map[cur.first][cur.second] == 1) {
            map[cur.first][cur.second] = 0;
            cnt++;
            continue;
        }

        for(int i=0;i<4;i++) {
            pair<int, int> next = {cur.first + direc[i][0], cur.second + direc[i][1]};

            if(isIn(next.first, next.second) && visited[next.first][next.second] != stage) {
                q.push(next);
                visited[next.first][next.second] = stage;
            }
        }
    }

    return cnt;
}

int main() {
    int cheeses = 0, ret, ans;
    scanf("%d %d", &N, &M);

    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++) {
            scanf("%d", &map[i][j]);
            if(map[i][j] == 1) cheeses++;
        }
    }

    while (cheeses > 0) {
        ans = cheeses;
        ret = meltdown(1,1,curStage++);
        cheeses -= ret;
    }

    printf("%d\n%d", curStage-1, ans);

    return 0;
}