[C/C++] 백준 #2636 치즈(깊이우선탐색)

이번 문제는 그래프 탐색 문제인데, 너비우선탐색을 사용해도 되고 깊이우선탐색을 사용해도 됩니다.  제 경우에는 깊이우선탐색(Depth First Search)을 이용해서 풀었습니다.

 

cheeze

 

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

 

문제에서 핵심은 공기가 있는 곳이라는 것을 확신할 수 있는 공간부터 시작을 하는 것입니다.  이 문제는 치즈의 공간에서 탐색을 하는 것이 아니고 공기 공간에서 탐색을 해서, 공기와 닿는 치즈를 다음번에 녹는다라고 표시하시면 됩니다.

 

제가 작성한 코드에서는 별도로 방문 표시를 배열을 잡아서 처리하지 않고, 그래프의 자료가 되는 맵에서 처리했습니다.  단지 탐색할 공간의 값을 매번 다르게 지정함으로써, 방문 배열을 초기화할 필요도 없고, 바로 처리할 수 있습니다.

 

제가 작성한 소스입니다.

 

//------------------------------------------------
//    baekjoon #2636 - Cheese
//        - by Aubrey Choi
//        - created at 2019-11-24
//------------------------------------------------
#include <stdio.h>

int v[100][100], n, m;
int dfs(int r, int c, int t)
{
    int d[][2] = { 0,1, 1,0, 0,-1, -1,0 }, ret=0, i;
    v[r][c]=t;
    for(i=0;i<4;i++)
    {
        int nr=r+d[i][0], nc=c+d[i][1];
        if(nr<0||nr>=n||nc<0||nc>=m||v[nr][nc]==t) continue;
        if(v[nr][nc]>t) { v[nr][nc]=t; ret++; continue; }
        ret+=dfs(nr,nc,t);
    }
    return ret;
}
int main()
{
    int i, j, u=0, p=0, last;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) for(j=0;j<m;j++)
    {
        scanf("%d",&v[i][j]);
        if(v[i][j]==1)v[i][j]=10000, u++;
    }
    while(u)
    {
        last=dfs(0, 0, ++p);
        u-=last;
        if(last==0) break;
    }
    printf("%d\n%d\n", p, last);
}

 

소스에서 dfs(..., int t)라고 정의한 부분에 보시면 t 값이 현재 탐색할 공간을 지정하는 값이 됩니다.  이와 같이 하면, 매번 탐색을 할 때마다 방문 배열을 초기화할 필요가 없어서 코드상으로도 간단해집니다.