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

백준의 배열에서 이동(1981) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 먼저 이분탐색으로 풀어야 하는 문제이다. 이분 탐색으로 탐색 가능한 범위냐 아니냐에 따라서 범위를 좁혀가면서

   탐색을 하면서 답을 도출해 내야 되는 문제이다.

   먼저 이분 탐색을 하기 위해서는 기준값이 필요하다. 보통 가장 작은 값과 가장 큰값을 2로 나눈 중간값을 기준값으로 설정

   한다. 따라서 본인은 입력을 받을 때, 가장 작은값과, 가장 큰 값을 찾아냈고, 그 두 값을 더해서 2로 나눈 값을 기준값으로

   설정해 주었다.

2) 이분탐색의 일반적인 구현 / 진행 방식을 이 문제에 맞춰서 어떻게 해야하는지 알아보자.

   1)에서 말했듯이 우리는 현재 가장 큰 값과 가장 작은 값을 찾아놓았다.

   그 2개의 값을 더해서 2로 나눈 값을 Mid(기준값) 으로 정하고, BFS()를 실행시키는 것이다.

  

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, Max_Value, Min_Value;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    Max_Value = -1;
    Min_Value = 500;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] > Max_Value) Max_Value = MAP[i][j];
            if (MAP[i][j] < Min_Value) Min_Value = MAP[i][j];
        }
    }
}
 
bool BFS(int Diff)
{
    queue<pair<int, int>> Q;
    
    for (int i = Min_Value; i <= Max_Value; i++)
    {
        memset(Visit, true, sizeof(Visit));
 
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                if (i <= MAP[j][k] && MAP[j][k] <= i + Diff) Visit[j][k] = false;
            }
        }
 
        Q.push(make_pair(0, 0));
 
        while (Q.empty() == 0)
        {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();
 
            if (Visit[x][y] == true) continue;
            Visit[x][y] = true;
 
            if (x == N - 1 && y == N - 1) return true;
 
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                if (nx >= 0 && ny >= 0 && nx < N && ny < N)
                {
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
    return false;
}
 
void Solution()
{
    int Start = 0;
    int End = Max_Value - Min_Value;
    int Mid;
 
    while (Start <= End)
    {
        Mid = (Start + End) / 2;
        if (BFS(Mid) == true) End = Mid - 1;
        else Start = Mid + 1;
    }
    cout << End + 1 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}