[백준] 1981번 배열에서 이동

1981 배열에서 이동

문제

---

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

---

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

출력

---

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

---

풀이)

BFS와 이분탐색을 이용해서 푸는 문제이다.

방법은 이러하다.

1. 배열상에서 가장 작은 값(min_num)과 가장 큰 값(max_num)을 구한다.

2. 허용하는 최소값과 최대값의 차이(=mid)를 이분탐색을 통해 구한다.

start = 0, end = max_num - min_num, mid = (start+end)/2

 2.1. 최소로 설정할 값(i)을 구한다.

      그리고 (i , i +  mid)사이의 값들을 BFS로 탐색하면서 [1,1]에서 [n,n]까지 이동가능한지 확인한다.

(이때 i는, 배열상에서 가장 작은 값(min_num)과 가장 큰 값(max_num) 사이의 값이다.)

 2.2 이동 가능하면 차이(mid)가 허용된다는 말이므로, mid값을 더 줄여본다.

      이동 불가능하면 차이(mid)가 부족하다는 말이므로, mid값을 더 늘린다.

3. 이동 가능했던 mid값 중 최소값을 출력한다.

주의사항

맨 처음 BFS를 시작하는 위치 [1,1]도 (i, i+mid)사이의 값이여야만 탐색 시작한다.

코드)

#include <stdio.h>
#include<string.h>
#include <queue>
using namespace std;
 
int n;
int map[101][101];
bool visited[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
bool bfs(int s, int e) {
    queue<pair<int, int>> qu;
    qu.push({ 1,1 });
    visited[1][1] = true;
    while (!qu.empty())
    {
        int y = qu.front().first;
        int x = qu.front().second;
        qu.pop();
        if (y == n && x == n) return true;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[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;
            qu.push({ ny,nx });
        }
    }
    return false;
}
 
int main() {
    scanf("%d",&n);
    int max_num = 0;
    int min_num = 987654321;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] > max_num) max_num = map[i][j];
            if (map[i][j] < min_num) min_num = map[i][j];
        }
    }
    int start = 0;
    int end = max_num - min_num;
    int mid;//차이값
    int result = 987654321;
    while (start <= end)
    {
        mid = (start + end) / 2; //최솟값과 최대값사이의 차이
 
        bool suc = false; //차이값 mid가 성립하는지
 
        
        for (int i = min_num; i <= max_num; i++) {//(i = 최솟값 i + mid = 최대값)이라고 할때
                                                //확인하려는 값들은 그 범위안에 무조건 들어야한다.
            
            if (i <= map[1][1] && map[1][1] <= i + mid) {//[1][1]이 그 범위안에 들으면
                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;
    }
    printf("%d", result);
    return 0;
}
 

+) 다른 분의 코드를 보니, visited[][]를 초기화 할때 무조건 다 초기화 하는것이 아니라

    (i, i~mid)내의 값들의 위치만 초기화하는 방법도 있었다.