[BaekJoon][1981] 배열에서 이동

BAEKJOON ONLINE JUDGE

 

1981 배열에서 이동

 

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

 

 

 

 

아 어렵다...

 

다이나믹도 해보고 dfs도 해보고 dfs 완탐은 time limit 나고. 뭐 time limit 날거라는 거는 예상했지만...

결국 해답 소스 보고함ㅠ

 

1. 이진 탐색으로 최대-최소 차이를 찾아나간다.

이진 탐색의 지표는 이진 탐색으로 정한 최대-최소 차이 내로 (1, 1)에서 (n, n)으로 갈 수 있느냐

(1, 1) -> (n, n) 갈 수 있느냐는 bfs로 탐색

2. bfs

최대-최소를 살펴보면서 가려면 지나온 경로들의 최대, 최소를 가지고 있어야 한다

but, 이렇게 접근하다가 다이나믹도, 완탐도 틀렸다ㅠ.ㅜ

=> map을 가장 작은 값에서 가장 작은 값 + 최대-최소 예상 값의 범위를 갖는 map으로 다시 조정한다.

     이렇게 한 후 (1, 1)에서 (n, n)으로 갈 수 있느냐는 아무 조건없는 bfs처럼 구현하면 된다.

 

이 때, 내가 알아채지 못해서 엄청 틀린 것이

visit[1][1] 이 만약 처음부터 범위에 속하지 못하면 시작도 못한다는 것이다.

이 점을 놓치면 안된다.

 

#include <cstdio>
#include <queue>
using namespace std;
 
#define INF    987654321
 
struct Point {
    int y, x;
};
 
int n;
int map[101][101];
int visit[101][101] = { 0, };
int lo = INF, hi = 0;
queue<Point > que;
 
void init()
{
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            visit[i][j] = 1;
        }
    }
 
    while (!que.empty())        que.pop();
}
 
int bfs(int limit)
{
    int dy[4] = { -1, 0, 0, 1 };
    int dx[4] = { 0, -1, 1, 0 };
    Point current;
 
    // 범위에 맞는 배열을 만들어 놓고 길이 있는지 보자
    for (int l = lo; l <= hi; l++) {
 
        init();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (map[i][j] < l)        visit[i][j] = 1;
                else if (map[i][j] >= l && map[i][j] <= l + limit)
                    visit[i][j] = 0;
                else visit[i][j] = 1;
            }
        }
 
        if (visit[1][1])    continue;
 
        visit[1][1] = 1;
        current.y = current.x = 1;
        que.push(current);
 
        while (!que.empty()) {
            current = que.front();
            que.pop();
 
            if (current.y == n && current.x == n)    return 1;
 
            for (int i = 0; i < 4; i++) {
                Point next;
 
                next.y = current.y + dy[i];
                next.x = current.x + dx[i];
 
                if (next.y > 0 && next.y <= n && next.x > 0 && next.x <= n
                     && visit[next.y][next.x] == 0) {
                    visit[next.y][next.x] = 1;
                    que.push(next);
                }
            }
        }
    }
 
    return 0;
}
 
int solve(int end)
{
    int start = 0;
    int middle;
    int res;
 
    while (start <= end) {
        middle = (start + end) / 2;
 
        if (bfs(middle))    end = middle - 1;
        else                start = middle + 1;
    }
 
    return end + 1;
}
 
int main()
{
    int i, j;
 
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%d", &map[i][j]);
 
            if (map[i][j] < lo)    lo = map[i][j];
            if (map[i][j] > hi)    hi = map[i][j];
        }
    }
 
    printf("%d\n", solve(hi - lo));
 
    return 0;
}
 

 

반응형