[C/C++] 백준 #2589 보물섬(너비 우선 탐색)

이번 문제는 너비 우선 탐색을 이용해서 풀었습니다.  플로이드 워샬을 이용해서 풀 수도 있겠지만, 모든 노드가 다 이어진 것이 아니기 때문에 같은 알고리즘 효율이라는 관점에서 너비 우선 탐색을 이용했습니다.

 

treasure island

 

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

2589번: 보물섬

 

문제는 섬안에서 최단거리로 가장 먼 두 점을 찾는 것입니다.  한칸의 거리가 모두 같기 때문에 다익스트라 알고리즘을 사용하지 않고, 너비 우선 탐색을 통해서도 충분합니다.  너비 우선 탐색의 깊이가 가장 깊은 곳을 탐색하면 되니까요.  문제는 모든 가능한 노드에서 너비 우선 탐색을 시도해야하기 때문에 알고리즘 효율은 \(O(N^3)\)이 될 수밖에 없습니다.  더 좋은 방법이 있을 것도 같지만, 좋은 생각은 떠오르지는 않았습니다.

 

제가 구현한 소스입니다.

//------------------------------------------------
//    baekjoon #2589
//        - by Aubrey Choi
//        - created at 2019-10-08
//------------------------------------------------
#include <stdio.h>
#include <memory.h>
#include <queue>

int main()
{
    int n, m, max=0, s, v[2500];
    char map[50][52];
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s", map[i]);
    for(int k=0;k<n*m;k++)
    {
        if(map[k/m][k%m]!='L') continue;
        std::queue<int> q;
        memset(v, 0xff, sizeof(v));
        q.push(k); v[k]=0;
        while(!q.empty())
        {
            s = q.front(); q.pop();
            int d[4][2]={0,1, 1,0, 0,-1, -1, 0};
            for(int i=0;i<4;i++)
            {
                int ny=(s/m)+d[i][0], nx=(s%m)+d[i][1];
                if(ny<0||ny>=n||nx<0||nx>=m||map[ny][nx]=='W'||v[ny*m+nx]!=-1) continue;
                q.push(ny*m+nx); v[ny*m+nx]=v[s]+1;
            }
        }
        if(v[s]>max) max=v[s];
    }
    printf("%d\n", max);
}