1981번 배열에서 이동

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

비슷한 문제 : https://www.acmicpc.net/problem/2842

bfs 이분 탐색 생각 집배원 한상덕 벡터 boj 이진 탐색 백준 복습 필수 코테

꼭 다시 풀어볼 문제이다.

처음 접근할 때, 그냥 단순 점과 점 사이의 거리로 접근하는 중에 알고보니 '경로' 중에 최댓값과 최솟값의 차이였다.

그래서 모든 각 원소들을 vector에 넣고 정렬 후에 중복 값들을 제거해준다.

그 후 Left와 Right를 활용하여 투 포인터나 이분 탐색스럽게 구현해주면 된다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 111
 
int n, m[Max][Max];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max];
vector<int> v;
 
bool bfs(int Left, int Right)
{
    if (m[0][0] < v[Left] || v[Right] < m[0][0]) {
        return false;
    }
 
    memset(visit, false, sizeof(visit));
    visit[0][0]= true;
 
    queue<pair<int, int> > q;
    q.push({ 0, 0 });
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (r == n - 1 && c == n - 1) {
                return true;
            }
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= n || x <0 || x >= n || visit[y][x] || m[y][x] < v[Left] || v[Right] < m[y][x]) {
                    continue;
                }
 
                visit[y][x] = true;
                q.push({ y, x });
            }
        }
    }
 
    return false;
}
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &m[i][j]);
            v.push_back(m[i][j]);
        }
    }
 
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
    int Left = 0, Right = 0, ans = 2e9;
 
    while (Left <= Right && Right < v.size())
    {        
        // 처음 진행 시에는 v[0](Left와 Right가 모두 0이므로)가 기준이므로 무조건 false이다.
        // false 시에는 그래서 Right를 증가시킨다.
        // 즉, 갈 수 있는 범위를 Right를 증가시키면서 갈 수 있는 경로(?)를 늘려가고,
        // 갈 수 있다면 Left를 증가시켜서 그 범위를 좁힌다.(Right와 Left의 격차를 줄이려고)
        if (bfs(Left, Right)) {
            ans = min(ans, v[Right] - v[Left]);
            ++Left;
        }
        else {
            ++Right;
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}