[C/C++] 백준 #2146 다리 만들기(DFS, BFS)

이번 문제는 최단거리를 찾는 문제이긴 하지만, 이동하는데 드는 비용이 항상 같기 때문에 너비 우선 탐색을 사용하면 되는 문제입니다.

 

문제는 아래의 링크입니다.

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

2146번: 다리 만들기

 

이 문제를 풀 때에는 두 단계를 걸쳐서 풀었습니다.

일단 섬마다 고유한 아이디를 부여하기 위해서 깊이우선탐색(DFS)을 이용해서 고유 아이디를 붙였습니다.

 

Identify islands

 

다음으로는 모든 섬에 대해서 다리를 놓기 위한 최단 거리를 구하는 작업을 하였습니다.  이 때에는 너비우선탐색(BFS)를 이용했습니다.

 

다른 섬에 도착하면 바로 종료하면 되는데, 지금 살펴보니 그 부분은 빠져 있네요.  어차피 수행시간은 0ms로 나와있어서, 크게 성능에 문제가 생기지는 않습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2146
//        - by Aubrey Choi
//        - created at 2019-11-01
//------------------------------------------------
#include <stdio.h>
#include <queue>

int map[10000], d[4][2]={0,1, 1,0, 0,-1, -1,0};
void dfs(int s, int n, int m)
{
    map[s]=m; int r=s/n, c=s%n;
    for(int i=0;i<4;i++)
    {
        int nr=r+d[i][0], nc=c+d[i][1], ns=nr*n+nc;
        if(nr<0||nr>=n||nc<0||nc>=n||map[ns]!=1) continue;
        dfs(nr*n+nc, n, m);
    }
}
int main()
{
    int n, i, s, t, r, cnt=2, ans=1000;
    scanf("%d",&n);
    for(i=0;i<n*n;i++) scanf("%d",&map[i]);
    for(i=0;i<n*n;i++) if(map[i]==1) dfs(i, n, cnt++);
    std::queue<int> q;
    for(i=0;i<n*n;i++) if(map[i]) q.push(i);
    while(!q.empty())
    {
        s = q.front(); q.pop(); t=map[s]>>16; r=map[s]&0xffff;
        for(i=0;i<4;i++)
        {
            int nr=(s/n)+d[i][0], nc=(s%n)+d[i][1], ns=nr*n+nc;
            if(nr<0||nr>=n||nc<0||nc>=n) continue;
            if(map[ns])
            {
                if((map[ns]&0xffff)!=r) if(ans > (t+(map[ns]>>16))) ans=t+(map[ns]>>16);
                continue;
            }
            map[ns]=((t+1)<<16)|r; q.push(ns);
        }
    }
    printf("%d\n",ans);
}