[백준 2636] 치즈 (C++)

문제

백준 2636

2636번: 치즈

풀이

전형적인 bfs 문제였습니다.

먼저 치즈의 개수를 세주고 temp에 저장합니다.

(0,0)은 무조건 공기이므로 bfs를 이용해 공기와 맞닿은 치즈들을 모두 공기로 바꿔줍니다.

다시 치즈의 개수를 세고, 치즈가 없다면 temp와 hour를 출력하고 있다면 bfs를 반복합니다.

소스 코드

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
 
int map[100][100];
bool visited[100][100];
int n, m;
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
int cnt = 0;
int temp = 0;
int hour = 0;
void bfs(int a, int b)
{
    if (visited[a][b])
        return;
    visited[a][b] = true;
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    while(!q.empty())
    {
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        if (map[y][x] == 0)
        {
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[ny][nx])
                {
                    visited[ny][nx] = true;
                    q.push(make_pair(ny, nx));
                }
            }
        }
        else
        {
            map[y][x] = 0;
        }
    }
}
 
int main()
{
    cin >> n >> m;
    bool checkzero = true;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
        }
    }
    while (1)
    {
        memset(visited, 0, sizeof(visited));
        cnt = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (map[i][j] == 1)
                    cnt++;
            }
        }
        if (cnt == 0)
        {
            cout << hour << endl;
            cout << temp << endl;
            break;
        }
        else
        {
            temp = cnt;
            bfs(0, 0);
            hour++;
        }
            
    }
    return 0;
}