배열에서 이동( BOJ 1981 )

문제 : https://www.acmicpc.net/problem/1981

1981번: 배열에서 이동

 

문제 파악하기

(1, 1)에서 (N, N)까지 이동하는 모든 경우 중 (최댓값-최솟값)이 가장 작은 경우를 구하는 문제입니다. 상하좌우 모든 방향으로 이동할 수 있으며, 100*100크기의 배열이기 때문에 모든 경우의 수를 구하는 건 불가능합니다. 그렇기에 적절하게 탐색의 범위를 조절해야 합니다.

 

문제 해결하기

문제를 해결하기 위해서는 (1, 1)에서 (N, N)까지 이동하되, 적절하게 불필요한 탐색을 없애야 합니다. 그렇다면 불필요한 탐색은 어떤 걸 의미할까요? 단순히 (x, y)를 방문했는지 체크하는건 의미 없습니다. (x, y)만을 체크하면 항상 먼저 도착한 값만을 탐색하고, 약간 돌아오지만 실제 정답인 값을 탐색하지 못 합니다. 그렇기에 몇 가지 값을 더 확인할 필요가 있습니다. 이 때, 적절한 값은 바로 지금까지 탐색한 최솟값과 최댓값입니다.

 

불필요한 탐색은 (x, y)에 도착했을 때의 최솟값과 최댓값을 가지고 판단할 수 있습니다. 만약 현재 최솟값을 가지고 있는 경우가 처음이라면  탐색을 계속할 필요가 있습니다. 하지만 현재 최솟값을 가지고 이미 (x, y)를 방문한 적이 있다면 우리는 이전의 최댓값과 현재 최댓값을 비교해야 합니다. 만약 현재 가지고 있는 최댓값이 이전의 최댓값보다 크다면 우리는 더이상 탐색할 필요가 없습니다. 현재 탐색할 값이 정답일 확률이 없기 때문입니다. 이렇게, 우리는 최솟값과 최댓값을 가지고 탐색을 진행할 여부를 판단할 수 있습니다.

 

그럼 (x, y)에 최솟값과 최댓값을 가지고 있었다는 걸 어떻게 표시할까요? 바로 3차원 배열을 사용하면 됩니다. 배열의 값은 0부터 200 사이의 값이기에 check[x][y][min]과 같이 배열을 충분히 만들 수 있습니다. 이 배열은 (x, y)에 min값을 가지고 있는 상태를 의미합니다. 그리고 check 배열에 지금까지의 최댓값을 저장하면 우리는 (x, y)에 방문했을 때의 최솟값과 최댓값을 모두 저장할 수 있습니다. 이후에는 배열의 값과 지금까지의 최댓값을 비교하여 탐색을 진행하고, (N, N)에 도착했을 때 결괏값을 비교하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <queue>
#include <algorithm>
#define NMAX 105
#define VMAX 205
using namespace std;
 
struct Pos {
    int x, y, vmax, vmin;
};
 
int N;
int inp[NMAX][NMAX];
 
queue< Pos > q;
 
int x, y, xx, yy, curMax, curMin, nxtMax, nxtMin;
int dx[4]={-1,0,1,0}, dy[4]={0,-1,0,1};
 
int ret;
int check[NMAX][NMAX][VMAX];
 
bool safe(int x, int y) {
    if(x<1 or y<1 or x>N or y>N) return 0;
    else return 1;
}
 
int main() {
    // input
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            scanf("%d", &inp[i][j]);
        }
    }
 
    // init
    ret = VMAX;
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            for(int k=0;k<VMAX;k++) {
                check[i][j][k] = VMAX;
            }
        }
    }
 
    q.push({1, 1, inp[1][1], inp[1][1]});
    check[1][1][inp[1][1]] = 1;
 
    // BFS
    while(!q.empty()) {
        x = q.front().x; y = q.front().y;
        curMax = q.front().vmax;
        curMin = q.front().vmin;
        q.pop();
 
        if(x == N and y == N) {
            ret = min( ret, curMax-curMin );
            continue;
        }
 
        for(int k=0;k<4;k++) {
            xx = x+dx[k]; yy = y+dy[k];
            nxtMax = max( curMax, inp[xx][yy] );
            nxtMin = min( curMin, inp[xx][yy] );
 
            if(safe(xx, yy) and nxtMax < check[xx][yy][nxtMin]) {
                q.push({xx, yy, nxtMax, nxtMin});
                check[xx][yy][nxtMin] = nxtMax;
            }
        }
    }
 
    // print
    printf("%d", ret);
}

후기

원래는 이분탐색으로 해결하려 했으나, 중간에 아이디어가 떠올라 3차원 배열을 사용하여 해결하게 된 문제입니다. 이분 탐색으로 해결하는 방법은 다른 사람들 소스코드를 보면서 생각해봐야겠습니다.