백준 1981번 배열에서 이동 - C++ 풀이

---

 

1. 파라매트릭 서치를 이용하여 가장 작은 gap을 찾는다.
2. maxVal - minVal = gap이 되는 모든 (minVal, maxVal) 쌍에 대하여, (1,1)에서 출발하여 minVal 이상 maxVal 이하인 칸들로만 (n, n)에 도착할 수 있는지 여부를 DFS/BFS를 사용하여 구한다.

 

1. 파라매트릭 서치를 이용하여 가장 작은 gap을 찾는다.

 (최대-최소) = gap이라 하자. 가장 작은 gap을 구하는 최적화 문제이다. 이를 결정문제로 바꾸어 줄 것이다. decision(gap)을 최대값과 최소값의 차가 gap 이하가 되도록 할 수 있는가로 정의하고, 이분탐색을 이용하여 최초로 가능한 gap을 찾는다.

 

2. maxVal - minVal = gap이 되는 모든 (minVal, maxVal) 쌍에 대하여, (1,1)에서 출발하여 minVal 이상 maxVal 이하인 칸들로만 (n, n)에 도착할 수 있는지 여부를 DFS/BFS를 사용하여 구한다.

 decision 함수는 maxVal - minVal = gap이 되는 모든 (minVal, maxVal) 쌍을 검사하는 것으로 구현할 수 있다. minVal, maxVal을 고정하고 난 뒤에는 DFS나 BFS를 사용하여 가능한 케이스인지 여부를 판단하면 된다.

 

반응형

---

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 987654321;

int N;
int board[100][100];
bool visit[100][100];

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

// DFS(r, c, minVal, maxVal)
//: 현재 (r, c)일 때, minVal이상 maxVal 이하인 칸들만 거쳐서 (N-1, N-1)에 도착가능한가
bool DFS(int r, int c, int minVal, int maxVal) {
    if (board[r][c] < minVal || board[r][c] > maxVal) return false;
    if (r == N-1 && c == N-1) return true;
    visit[r][c] = true;
    
    for (int i=0; i<4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
        if (visit[nr][nc]) continue;
        
        if (DFS(nr, nc, minVal, maxVal)) return true;
    }
    
    return false;
}

// decision(gap): 최대값과 최소값의 차가 gap이하가 되도록 할 수 있는가
bool decision(int gap) {
    for (int i=0; i<=200-gap; i++) {
        memset(visit, 0, sizeof(visit));
        if (DFS(0, 0, i, i+gap)) return true;    
    }
    
    return false;
}

int optimize() {
    int lo = -1, hi = 200;
    
    while (lo+1 < hi) {
        int mid = (lo+hi)/2;
        if (decision(mid)) hi = mid;
        else lo = mid;
    }
    
    return hi;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> board[i][j];
        }
    }
    
    cout << optimize();

    return 0;
}