백준 - 치즈 (2638)

2638번: 치즈

접근

MxN 크기의 판에 놓여 있는 치즈들이 전부 녹아 없어지는 데 걸리는 시간을 구하는 문제 입니다. 치즈가 녹아 없어지는 조건이 두 개 이상의 변이 외부 공기에 노출되어 있는 경우 입니다.

그렇다면 2차원 배열을 일일히 탐색해서 두 변 이상이 노출되면 치즈를 없애는 방향으로 반복하면 풀리는 문제 처럼 보이겠지만, 조건이 하나 더 붙어 있습니다

 

치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않은 것으로 간주한다.

 

치즈 내부에 있는 비어있는 부분들, 그러니까 안쪽에 비어있는 부분들은 공기로 취급하지 않기 때문에 치즈가 녹는것에 영항을 주지 않는다는 얘기 입니다.

예를 들어, 위 그림의 정 가운데에 있는 치즈는 4면이 전부 다 공기와 접촉해 있는 것처럼 보이지만, 주위에 둘러싸여 있는 치즈들로 인해 정 가운데에 있는 치즈는 공기의 영항을 받지 않아 녹지 않게 됩니다.

 

따라서 그래프 탐색을 할 때 치즈 우선으로 탐색하기 보다는 외부 공기로 취급되는 빈칸들을 BFS로 탐색한 다음, 치즈들이 외부 공기와 몇 개의 변이 접촉하는 지를 확인해야 합니다.

 

알고리즘

백준 두번 째 예제 문제

예를 들어 아래와 같이 치즈가 배치되어 있습니다. 우선 외부 공기가 들어있는 빈 칸을 탐색합니다. BFS를 이용해도 되고 DFS를 이용해도 됩니다.

파란 색이 외부 공기 입니다. 안쪽의 빈칸은 치즈라는 벽에 막혀 있으므로 외부 공기가 들어오지 않습니다.

그다음 외부 공기에 변이 2개 이상 노출되어 있는 치즈를 찾아 제거합니다. 이때는 그냥 치즈만 찾으면 되므로 2차원 배열을 순회하기만 하면 됩니다.

다시 아까와 같은 방식으로  진행을 합니다.

이렇게 해서 치즈를 지우는데 총 3이라는 시간이 걸리게 됩니다.

 

수도 코드

Function Process
	ans <- 0
	While
    		외부공기_탐색
        	외부_공기와_접촉되어_있는_치즈_확인_및_제거
        	if 제거된_치즈 = 0 then
			break
		else then
			ans <- ans + 1
		endIf
    	endWhile
endFunction

C++ 코드

#include <iostream>
#include <queue>
using namespace std;

int di[4] = {0, 0, -1, 1};
int dj[4] = {1, -1, 0, 0};

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int N, M, G[100][100], V[100][100], cnt;
    cin >> N >> M;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cin >> G[i][j];
            V[i][j] = 0;
        }
    }

    // 정답
    cnt = 0;

    while(1)
    {
        // BFS를 이용하여 바깥 공기가 접해있는 칸을 조사
        queue<pair<int, int>> q;
        q.push(make_pair(0, 0));
        V[0][0] = cnt+1;
        while(!q.empty())
        {
            pair<int, int> e = q.front();
            q.pop();
            int i = e.first, j = e.second;
            for(int k=0; k<4; k++)
            {
                int ni = i+di[k], nj = j+dj[k];
                // 범위 밖
                if(!((0<=ni&&ni<N)&&(0<=nj&&nj<M))) continue;
                // 벽 여부와 방문 여부
                if(G[ni][nj] || V[ni][nj] == cnt+1) continue;
                V[ni][nj] = cnt+1;
                q.push(make_pair(ni, nj));
            }
        }

        // 바깥공기와 두 면 이상이 접해 있는 치즈 없애기
        int removed = 0;
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<M; j++)
            {
                if(G[i][j])
                {
                    int a = 0;
                    for(int k=0; k<4; k++)
                    {
                        int ni = i+di[k], nj = j+dj[k];
                        if(V[ni][nj] == cnt+1) a++;
                    }
                    if(a>=2)
                    {
                        G[i][j] = 0;
                        removed++;
                    }
                }
            }
        }
        if(removed==0) break;
        cnt++;
    }
    cout << cnt << '\n';
    return 0;
}