[C/C++] 백준 #1981 배열에서 이동(이분탐색)

이번 문제는 보통의 그래프 문제와 다르게 경로상의 최저값과 최고값의 차이가 가장 적게 나오는 경로에서의 그 차이를 출력하는 문제입니다.  최저값과 최고값의 차이를 가지고 다루는 문제이기 때문에 다익스트라 알고리즘과 같은 탐욕 알고리즘 기반을 사용할 수가 없습니다.

 

Binary Search

 

제가 접근한 방법은 최고값과 최저값의 차이를 주어지고, 깊이우선 탐색(DFS)을 통해서, 시작점과 끝점까지 가는데, 그 차이를 가지는 경로가 있는지 확인하도록 했습니다.  최고값과 최저값의 차이는 이분탐색을 이용했습니다.

 

제일 먼저 모든 간선값들의 최저값과 최고값을 찾아서 그 차이값을 상한값으로 하였습니다.  이 값은 반드시 경로가 존재하게 되겠죠.  그리고 경로가 존재할 수 없는 값은 -1이 되겠죠.  모든 간선값이 같은 경우에는 0이 나와야 하니까요.  이것을 이용해서 이분탐색으로 했습니다.  최대 차이값이 D라고 한다면 이분탐색을 하는데 걸리는 시간복잡도는 \(O(\log D)\)이 됩니다.  깊이우선탐색을 매번 해야 하므로 전체적인 시간 복잡도는 \(O(N^2 \log D)\)가 됩니다.  N의 최대값이 100정도이므로 이 알고리즘으로 충분한 해를 구할 수가 있습니다.

 

깊이우선탐색을 할 때에는 오른쪽과 아래방향에 우선순위를 두었기 때문에 경로를 찾을 때, 가능하면 빨리 경로를 찾을 수 있게 하였습니다.

 

제가 작성한 소스입니다.

//--------------------------------------
//    baekjoon #1981
//        - by Aubrey Choi
//        - created at 2020-02-03
//--------------------------------------
#include <stdio.h>

int map[102][102], n, v[102][102];
bool dfs(int r, int c, int min, int max, int m)
{
    const int d[][2]={0,1, 1,0, 0,-1, -1,0};
    if(r==n&&c==n) return true;
    v[r][c]=m;
    for(int i=0;i<4;i++)
    {
        int nr=r+d[i][0], nc=c+d[i][1], s=map[nr][nc];
        if(s<min||s>max||v[nr][nc]==m) continue;
        if(dfs(nr, nc, min, max, m)) return true;
    }
    return false;
}
int main()
{
    int i, j, min, max, t=1;
    scanf("%d",&n);
    for(i=1;i<=n;i++) map[0][i]=map[n+1][i]=map[i][0]=map[i][n+1]=-1;
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&map[i][j]);
    min=(map[1][1]<map[n][n])?map[1][1]:map[n][n];
    max=(map[1][1]>map[n][n])?map[1][1]:map[n][n];
    i=max-min-1, j=200;
    while(i+1<j)
    {
        int c=(i+j)/2, k=(max<c)?0:max-c, u=(min+c>200)?200-c:min;
        for(;k<=min;k++) if(dfs(1, 1, k, k+c, t++)) break;
        if(k<=min) j=c; else i=c;
    }
    printf("%d\n", j);
}