백준 1981 배열에서의 이동

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int board[100][100], n;


int dx[]={1, -1, 0, 0}, dy[]={0,0,-1,1};

bool isRange(int x, int y) {
    return x>=0 && x<n && y>=0 && y<n;
}

// 잘못짰다고... ㅠ _ ㅠ
bool canGo(int x, int y, int k) {
    for(int low=0; low<=200; ++low) {
        if(board[x][y]<low || board[x][y]>low+k)
            continue;
        bool visited[100][100] = {false,};
        queue<pair<int, int>> q;
        visited[x][y] = true;
        q.push({x, y});
        while (!q.empty()) {
            pair<int, int> here = q.front();
            q.pop();
            if (here.first == n - 1 && here.second == n - 1)
                return true;
            for (int i = 0; i < 4; ++i) {
                pair<int, int> there = {here.first + dx[i], here.second + dy[i]};
                if (!isRange(there.first, there.second))
                    continue;
                if (visited[there.first][there.second])
                    continue;
                if (board[there.first][there.second] < low || board[there.first][there.second] > low + k)
                    continue;
                q.push(there);
                visited[there.first][there.second] = true;
            }
        }
    }
    return false;
}

int main() {
    cin>>n;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            cin>>board[i][j];
        }
    }
    int lo=-1, hi=200;  //lo=false , hi=true;
    while(lo+1<hi) {
        int mid=(lo+hi)/2;
        if(canGo(0, 0, mid)) {
            hi=mid;
        } else
            lo=mid;
    }
    cout<<hi;
    //std::cout << "Hello, World!" << std::endl;
    return 0;
}

bool isRange(int h, int w) {
    if(h < 0 || w < 0 || h >= n || w >= n) return false;
    else return true;
}


int  isPossible(int limit, const vector<vector<int> > &board) {
    int mmove[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    priority_queue<comp> que;
    vector<vector<bool> > visited(n, vector<bool>(n, false));
    que.push(comp(0,0, board[0][0]));
    while(!que.empty()) {
        int nowH = que.top().h;
        int nowW = que.top().w;
        int nowV = que.top().c;
        que.pop();
        if(nowH == n- 1 && nowW == n-1) return nowV;
        for(int i = 0; i < 4; i++) {
            int nextH = nowH + mmove[i][0];
            int nextW = nowW + mmove[i][1];
            if(isRange(nextH, nextW)) {
                int nextV = max(board[nextH][nextW], nowV);
                if(board[nextH][nextW] >= limit && visited[nextH][nextW] == false) {
                    que.push(comp(nextH, nextW, nextV));
                    visited[nextH][nextW] = true;
                }
            }
        }
    }
    return 2000;
}

int main() {
    cin >> n;
    vector<vector<int> > board(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d",  &board[i][j]);
        }
    }

    int ans = INF;

    for(int i = 0; i <= board[0][0]; i++) {
        ans = min(isPossible(i, board) - i, ans);
    }
    cout << ans << endl;
}

#include<cstdio>
#include<algorithm>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, cnt, p[10000], r = 999;
pair<int, int> s[10000];
int f(int h) { return h^p[h] ? p[h] = f(p[h]) : h; }
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) s[cnt].second = i*n + j, scanf("%d", &s[cnt++].first);
    sort(s, s + cnt);
    for (int i = 0; i <= 200; i++) {
        int ck[100][100] = { 0, };
        for (int j = 0; j < n*n; j++) p[j] = j;
        for (int j = 0; j < cnt; j++) if (s[j].first >= i) {
            ck[s[j].second / n][s[j].second%n] = 1;
            for (int k = 0; k < 4; k++) {
                int tx = s[j].second / n + fx[k], ty = s[j].second%n + fy[k];
                if (tx >= 0 && ty >= 0 && tx < n && ty < n && ck[tx][ty]) p[f(tx*n + ty)] = f(s[j].second);
            }
            if (f(0) == f(n*n - 1)) { r = min(r, s[j].first - i); break; }
        }
    }
    printf("%d", r);
    return 0;
}