[C/C++] 백준 #1743 음식물 피하기(너비우선탐색)

이번 문제는 섬의 개수 구하기라든지, 섬의 넓이 구하기 문제와 비슷한 유형으로 너비 우선 탐색(BFS)나 깊이 우선 탐색(DFS)를 이용해서 푸시면 됩니다.

 

 

구현 자체는 깊이 우선 탐색이 더 쉽습니다.  너비 우선 탐색은 일단 큐를 사용해야 하기때문에 구현이 조금 더 까다롭다고 볼 수 있습니다.  그에 비해서 깊이 우선 탐색을 이용하면 재귀함수만 이용하면 되죠.  구현도 훨씬 간단하고요.

 

 

제가 작성한 소스입니다.  소스는 참고로 봐주세요.

//--------------------------------------------------------------------
//    baekjoon #1743 - Avoid The Lakes
//        - by Aubrey Choi
//        - created at 2019-08-06
//--------------------------------------------------------------------
#include <stdio.h>
#include <queue>

int main()
{
    int n, m, k, r, c, max=0;
    static char v[100][100];
    scanf("%d%d%d",&n,&m,&k);
    while(k--) { scanf("%d%d",&r,&c); v[r-1][c-1]=1; }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(v[i][j]==0) continue;
            std::queue<int> q;
            int cnt=0;
            q.push(i*100+j);
            v[i][j]=0;
            while(!q.empty())
            {
                r=q.front()/100; c=q.front()%100; q.pop();
                cnt++;
                int d[4][2]={ 0, 1, 1, 0, 0, -1, -1, 0 };
                for(int s=0;s<4;s++)
                {
                    int nr=r+d[s][0], nc=c+d[s][1];
                    if(nr<0||nr>=n||nc<0||nc>=m||!v[nr][nc]) continue;
                    q.push(nr*100+nc);
                    v[nr][nc]=0;
                }
            }
            if(cnt>max) max=cnt;
        }
    }
    printf("%d\n", max);
}