[1981번] 배열에서 이동

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

2. 이분 탐색

우선 이문제는 BFS + 이분탐색 문제로 해결 할 수 있다.

이분탐색을 쓰는 부분은 정답이 어떻게 될지에 대해 이용을 하면 된다.

즉, 최댓값과 최솟값 차이가 가장 작아질 값을 미리 이분탐색으로 정해두고 시작한다.

그다음 BFS는 그 값을 이용하여 0,0에서 N-1,N-1로 도착할 수 있는지 확인만 시켜주면 된다.

물론 지금까지는 이해도되고 문제를 금방 풀 수 있을 것 같다.

하지만 고려해야할 상황이 있다. BFS를 이용할 때 이미 방문한 정점들을 어떻게 처리해줘야할 지 생각해야한다.

그에 따른 해결 방법은 다음과 같다.

입력을 받을때 미리 입력의 최솟값과 최댓값을 구해둔다.

그다음 최댓값 - 최솟값 = 이분탐색값이니 최댓값 = 최솟값 + 이분탐색값이 될것이다.  

따라서 for문을 이용하여 bot라는 변수를 두어 최솟값부터 시작하여 

최댓값 >= 최솟값 + 이분탐색값이 되어야 한다는 점을 이용하여 문제를 해결 할 수 있다.

최종적으로 N-1, N-1에 도착하게된다면 그것이 결국 현재 이분탐색값으로 도착할 수 있다는 것을 의미하게 된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <memory.h>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int arr[102][102];
bool visit[102][102];
 
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };
int main()
{
    int n;
    int min_val = 500;
    int max_val = 0;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &arr[i][j]);
            min_val = min(min_val, arr[i][j]);
            max_val = max(max_val, arr[i][j]);
        }
 
    int start = 0, end = 200;
    int get = 500;
 
    while (start <= end)
    {
        int mid = (start + end) / 2;
 
        bool in = false;
        bool out = false;
        for (int bot = min_val; bot + mid <= max_val; bot++)
        {
            in = true;
 
            if (out)
                break;
 
            memset(visit, 0, sizeof(visit));
 
            if (arr[0][0] < bot || arr[0][0] > bot + mid)
                continue;
 
            queue<pii> q;
 
            q.push({ 0,0 });
            while (!q.empty())
            {
                int y = q.front().first;
                int x = q.front().second;
 
                q.pop();
 
                if (visit[y][x])
                    continue;
 
                visit[y][x] = true;
 
                for (int i = 0; i < 4; i++)
                {
                    int ny = dy[i] + y;
                    int nx = dx[i] + x;
 
                    if (!((0 <= ny && ny < n) && (0 <= nx && nx < n)))
                        continue;
 
                    if (visit[ny][nx])
                        continue;
 
                    if (arr[ny][nx] < bot || arr[ny][nx] > bot + mid)
                        continue;
 
                    q.push({ ny,nx });
 
                    if (ny == n - 1 && nx == n - 1)
                        out = true;
                }
            }
        }
 
        if (!in || out)
        {
            get = min(mid, get);
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
    printf("%d", get);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>