[백준]배열에서 이동(1981)

문제 링크 : [백준]배열에서 이동(1981)

문제 설명

N * N의 2차원 배열에 각각 0 ~ 200의 숫자가 주어집니다.
(1,1)에서 (N,N)까지 이동(위, 아래, 왼쪽, 오른쪽으로 이동 가능)하면서 지나간 수 중 최대값과 최소값의 차이가 최소가 되는 값을 구하세요.

입력

N(배열의 크기, 1 <= N <= 100)
V_ij(각 배열의 값, 0 <= V <= 200)

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

출력

2

카테고리

#BFS #투포인터

시간 복잡도 상한

O(N³)

해결 방법

1. 브루트포스로 풀기에도 굉장히 난해한 문제입니다.
2. 구간의 상한과 하한을 정해놓고 그 값들만 밟아가면서 BFS를 이용해 풀면 가능할 것 같습니다.
3. 시간복잡도는 BFS가 O(N²)에, 각 경우가, 200²이니까 타임아웃입니다.
4. 그런데 모든 경우를 다 구할 필요가 있나 생각을 해봅니다.
5. 1 ~ 5까지 구간으로 성공했다면, 1 ~ 6까지의 구간은 확인할 필요가 없습니다.
6. 이미 성공한 최단 구간(최대와 최소값의 차이가 최소인 구간)보다 더 큰 구간은 당연히 성공하겠지만, 그 값은 항상 최소값보다 크기 때문입니다.
7. 반대로 10 ~ 15가 성공했다면, 9 ~ 15도 확인할 필요가 없습니다.
8. 따라서 최대, 최소값의 구간을 0, 0에서 시작하여, 실패한다면 최대값을, 성공한다면 최소값을 증가시켜, 성공하는 최단 구간을 구하면 됩니다.
9. 시간복잡도는 최대값이 이동하는 200, 최소값이 이동하는 200, 합쳐서 200 * N²이므로 시간은 충분합니다.

시간복잡도

O(N² * 400)

코드

#include<cstdio>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int>P;
int n,d[102][102],i,j,l,r,a=201,o[4][2]={{1,0},{-1,0},{0,1},{0,-1}},v[102][102];
queue<P>q;
int c(){
    while(!q.empty())q.pop();
    if(d[1][1]<l||d[1][1]>r)return 0;
    q.push({1,1});
    memset(v,0,sizeof(v));
    v[1][1]=1;
    while(!q.empty()){
        P c=q.front();q.pop();
        for(i=0;i<4;i++){
            int nx=c.first+o[i][0],ny=c.second+o[i][1];
            if(!v[nx][ny]&&d[nx][ny]<=r&&d[nx][ny]>=l){
                if(nx==n&&ny==n)return 1;
                v[nx][ny]=1;
                q.push({nx,ny});
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    for(i=0;i<102;i++)for(j=0;j<102;j++)d[i][j]=202;
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",d[i]+j);
    while(r<201){
        if(c())a=min(r-l,a),l++;
        else r++;
    }
    printf("%d",a);
}