백준 1981번 배열에서 이동

배열에서 이동 

문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(2≤n≤100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.

처음에는 단순히 bfs로 완전탐색을 하면서 최소와 최대값을 찾아 차를 구해주었는데 이렇게 하니까 당연히 시간초과가 났다. 
이것을 해결하기 위해 최솟값과 최댓값의 간격을 이분탐색으로 줄여나가면서 해당 간격안에 최댓값 - 최솟값이 들어있음과 동시에 (n,n)에 도달할 수 있는 지 확인하는 방법으로 풀었다.

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
 
int map[101][101];
bool visited[101][101];
int n;
int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };

bool bfs(int s, int e){
    queue<pair<int,int>> q;
    q.push({1,1});
    visited[1][1] = true;
    
    while(!q.empty()){
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        if(y ==n && x ==n){
            return true;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > n || visited[ny][nx]){
                continue;
            }
            if(map[ny][nx] < s || map[ny][nx] > e){
                continue;
            }
            visited[ny][nx] = true;
            q.push({ny,nx});
        }
    }
    return false;
}
int main() {
    
    cin >> n;
    int MAX = 0;
    int MIN = 1000000000;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> map[i][j];
            if(map[i][j] > MAX) {
                MAX = map[i][j];
            }
            if(map[i][j] < MIN){
                MIN = map[i][j];
            }
        }
    }
        int start =0;
        int end = MAX - MIN;
        int mid;
        int result = 1000000000;
        while( start <= end){
            mid = (start + end)/2;
            bool suc = false;
            
            for(int i=MIN; i<= MAX; i++){
                if(i <= map[1][1] && map[1][1] <= i + mid) {
                    bool check = bfs(i, i+ mid);
                    memset(visited, false, sizeof(visited));
                    if(check) {
                        suc = true;
                        break;
                    }
                }
            }
            
            if(suc) {
                if(result > mid){
                    result = mid;
                    end = mid -1;
                }
            }else {
                start = mid + 1;
            }
        }
    cout << result;
    return 0;
}