[ 백준 ] 2638번 - 치즈 (C++)

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

2638번: 치즈

 

 

[ 문제풀이 ]

 

BFS를 이용한 구현 문제였습니다.

 

주어진 모눈종이의 테두리는 치즈가 없다고 하였으므로 0, 0부터 BFS를 돌려 치즈로 둘러싸여 있지 않은 공간들을 2로 초기화시켜주고 치즈들 중 2칸 이상 2에 닿아있는 치즈는 녹이면서 진행하였습니다.

 

그리고 다시 0, 0부터 BFS를 돌려 빈 공간들을 2로 초기화시켜주면서 위의 과정을 반복하고, 치즈가 다 사라지면 BFS를 돌린 횟수를 출력하였습니다.

 

[ 소스 코드 ]

#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M;
int map[100][100];
int visited[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
void bfs(int y, int x)        //치즈에 둘러쌓여 있지 않은 공간을 2로 초기화
{
    queue<pos> q;
    memset(visited, 0, sizeof(visited));
    q.push({ y,x });
    visited[y][x] = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        map[curY][curX] = 2;
 
        for (int i = 0; i < 4; i++) {
            int yy = curY + dy[i];
            int xx = curX + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (map[yy][xx] != 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int check()        //치즈가 다 녹았는지 체크하는 함수
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 1) {
                return 0;
            }
        }
    }
 
    return 1;
}
 
int Cnt(int y, int x)    //실내 온도에 노출 된 횟수를 출력
{
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
            if (map[yy][xx] == 2) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
 
    int cnt = 0;
 
    while (!check())        //치즈가 다 녹을 때까지
    {
        bfs(0, 0);        //0, 0부터 2로 빈 공간 2로 초기화
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {    //2칸 이상 닿아있다면 녹임
                    if (Cnt(i, j) >= 2) {
                        map[i][j] = 0;
                    }
                }
            }
        }
 
        cnt++;        //횟수 추가
    }
 
    cout << cnt;
}