[BOJ] 2636 치즈 with C++

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

2636번: 치즈

 

이 글은 BOJ 2636 치즈를 C++ 로 풀이한 글입니다.

풀이

문제를 보면 기본적으로 전형적인 그래프 탐색 알고리즘 문제라는 것을 알 수 있다. 

기본적으로 매커니즘은 공기 접촉 -> 접촉 치즈 사라짐 -> 공기 접촉 -> 치즈 사라짐을 반복된다.

문제에서 요구하는 것은 최종 걸리는 시간과 마지막 한 시간 전 치즈의 양이다. 

 

매시간에 동시에 치즈가 없어져야 하므로 처음 접근은 DFS로 외곽에 존재하는 모든 공기층을 탐색하고 외곽 공기층에 붙어 있는 치즈를 큐에 넣은 후 들어간 값을 하나씩 빼면서 BFS진행하는 것이었다. 하지만 문제점은 치즈안에 있는 구멍과 만나게 될 경우 구멍과 접촉된 모든 치즈도 동시에 큐에 들어가야 한다는 점이었다. 

 

따라서 치즈가 사라져 구멍이 공기층과 만났을 때를 적적히 처리하는 것이 핵심이었다.

테투리는 무조건 공기층임으로 (0, 0) 기준으로 DFS를 통해 공기층과 그에 붙어 있는 치즈를 모두 탐색하고 치즈만을 치즈를 큐에 넣는다. 이 때 큐에 시간도 함께 넣어준다.

큐에 넣은 치즈를 모두 공기로 변경하고 큐에 들어와 있는 점을 기준으로 DFS를 다시 진행하여 구멍과 만났을 경우 구멍에 해당하는 공기를 모두 탐색하고 구멍에 붙어있는 치즈 또한 모두 큐에 넣어서 함께 탐색할 수 있도록 구현하였다.

 

또한 치즈가 공기로 변경될 때마다 매 시간 최종시간을 업데이트 해주고

DFS 탐색을 통해 치즈가 발견되어 큐에 들어갈 때마다 해당 시간에 큐에 들어간 치즈를 양을 기록해준다.

 

최종시간을 출력하고 최종시간에 큐에 들어간 치즈를 양이 마지막까지 남아 있던 치즈의 양이므로 이를 출력한다. 

 

 

코드

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int n, m, maxDep = 0;
int board[100][100];
bool visited[100][100] = {0};
int cnt[200] = {0};

queue<tuple<int, int, int>> q;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

void DFS(int x, int y, int dep)
{
    for (int dir = 0; dir < 4; dir++)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m)
            continue;
        if (visited[nx][ny])
            continue;
        if (board[nx][ny] == 0)
        {
            visited[nx][ny] = true;
            DFS(nx, ny, dep);
        }
        else
        {
            visited[nx][ny] = true;
            cnt[dep + 1] += 1;
            q.push(make_tuple(nx, ny, dep + 1));
        }
    }
}

void BFS()
{
    visited[0][0] = true;
    q.push(make_tuple(0, 0, 0));

    int x, y, dep;
    while (!q.empty())
    {
        tie(x, y, dep) = q.front();
        q.pop();
        maxDep = max(maxDep, dep);
        board[x][y] = 0;
        DFS(x, y, dep);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];

    BFS();
    cout << maxDep << '\n';
    cout << cnt[maxDep];
    return 0;
}