백준 1981번: 배열에서 이동 (C++)

접근

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

1981번: 배열에서 이동

이분탐색과 BFS 알고리즘을 이용하는 문제였다. 이분탐색을 통해 간격을 줄여가며 최대-최소 값이 될 수 있는 최소 값을 찾는다. 탐색하는 중에 해당 값으로 (1, 1) 에서 (N, N) 으로 도달할 수 있는지 탐색하는데 BFS 알고리즘을 이용한다.

처음에는 DFS 탐색을 통해 최대 최소값을 갱신해가면서 문제를 풀어보려고 했지만, 시간 초과로 문제를 해결할 수 없었다.

void dfs(int r, int c, int tmpMax, int tmpMin) {
    if (ans < tmpMax - tmpMin) return;
    int val = MAP[r][c];
    if (r == N - 1 && c == N - 1) {
        ans = max(tmpMax, val) - min(tmpMin, val);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (MapOut(nr, nc) || Visited[nr][nc] == 1) continue;
        Visited[nr][nc] = 1;
        dfs(nr, nc, max(tmpMax, val), min(tmpMin, val));
        Visited[nr][nc] = 0;
    }

하지만 제대로 해결하지 못하고, 탐색의 경우의 수를 줄이기 위해 이분탐색을 이용하게 되었다.

코드

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define endl '\n'
#define MAX_N 101
#define INF 987654321

int N, MaxVal = INF, MinVal = 0;
int MAP[MAX_N][MAX_N];
int Visited[MAX_N][MAX_N];

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

int max(int a, int b) {
    if (a >= b) {
        return a;
    } else {
        return b;
    }
}

int min(int a, int b) {
    if (a <= b) {
        return a;
    } else {
        return b;
    }
}

bool MapOut(int r, int c) {
    return (r < 0 || N <= r || c < 0 || N <= c);
}

// 간격이 mid 값일 때, MAP[0][0]에서 MAP[N - 1][N - 1]까지 이동할 수 있는지 경로를 탐색하는 함수
int bfs(int mid) {
    int start_val = MAP[0][0];
    int end_val = MAP[N - 1][N - 1];
    int low = max(MinVal, max(start_val, end_val) - mid);
    int high = min(MaxVal - mid, min(start_val, end_val));
    for (int i = low; i <= high ; i++) {
        memset(Visited, 0, sizeof(Visited));
        queue<pair<int, int>> Q;
        Q.push(make_pair(0, 0));
        Visited[0][0] = 1;
        while (Q.empty() == 0) {
            int r = Q.front().first;
            int c = Q.front().second;
            Q.pop();
            for (int j = 0; j < 4; j++) {
                int nr = r + dr[j];
                int nc = c + dc[j];
                if (MapOut(nr, nc) || MAP[nr][nc] < i || i + mid < MAP[nr][nc] || Visited[nr][nc] == 1) continue;
                if (nr == N - 1 && nc == N - 1) return 1;
                Visited[nr][nc] = 1;
                Q.push(make_pair(nr, nc));
            }
        }
    }
    return 0;
}

// 이분탐색을 통해 (최대-최소) 값을 구하는 함수
int Solve() {
    int Start = 0;
    int End = MaxVal - MinVal;
    int Mid;

    while (Start <= End) {
        Mid = (Start + End) / 2;
        if (bfs(Mid)) {
            End = Mid - 1;
        } else {
            Start = Mid + 1;
        }
    }
    return End + 1;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i][j];
            MaxVal = max(MaxVal, MAP[i][j]);
            MinVal = min(MinVal, MAP[i][j]);
        }
    }

    cout << Solve() << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!