[BaekJoon][2842] 집배원 한상덕

BAEKJOON ONLINE JUDGE

2842 집배원 한상덕

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

처음 접하는 이진탐색... 이라고 해야하나

일단 처음 풀이는 이진 탐색 문제집에서 열어본 문제기 때문에 이진탐색이라는 점을 염두해 두고 풀이를 접근해 보았다. 또한 이전에 풀었던 '배열에서 이동' 문제가 생각나서 이와 비슷한 문제라고 생각을 하였다.

but, '배열에서 이동'처럼 문제를 접근하기에는 고도 값이 매우 크기 때문에 time limit이 날 수 밖에 없다.

1. 다익스트라

 일단 이진탐색으로 고도의 최소값을 정해놓고, 그 중 P에서 K로 가는 경로의 최대값을 파악했다.

될 수 있는 최소 고도의 최대값을 이진탐색으로 찾고, 0부터 최소 고도의 최대값까지 다익스트라를 돌리면서 이 중 피로도가 최소인 값을 정답으로 하였다.

최대값을 정하지 않고 최소값 구하기 위한 이진탐색은 기준이 되는 최소값 보다 큰 값을 고도로 갖는 경로 중에서 배달을 완수할 수 있는지의 여부로 탐색하였다.

=> 최소 고도의 최대값을 찾았다고 해서 피로도가 최소는 아니다!

이진탐색으로 구한 값은 경로 고도의 최소값이 [range[0], range[e]]에 속하면 갈 수 있다는 뜻이므로, 이 경우를 모두 돌아보며 피로도의 최소를 구해야 한다.

또한 여기서 중요한 것이

문제의 정답이 될 수 있는 최대, 최소 고도는 입력으로 받는 고도값 중 하나가 될 것이다.

따라서 이진탐색의 탐색 범위를 고도 값이 아닌 입력받은 고도값으로 탐색을 해 나가면 시간을 훨씬 줄일 수 있다.

-> 452ms

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
 
struct Point {
    int y, x;
};
 
int n;
char inputMap[55][55];
int height[55][55];
int starty, startx;
int visit[55][55];
int sz;
int range[2600];
Point point[2600];
int ans = 1e9;
 
int dijkstra(int num) {
 
    int map[55][55];
    int state[55][55];
 
    int dy[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };
    int dx[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
 
    if (height[starty][startx] < num)    return 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            visit[i][j] = 1e9;
            map[i][j] = state[i][j] = 0;
            if (height[i][j] >= num)        map[i][j] = 1;
        }
    }
 
    priority_queue<pair<int, pair<int, int> > > que;
    visit[starty][startx] = height[starty][startx];
    que.push(make_pair(height[starty][startx] * -1, make_pair(starty, startx)));
 
    while (!que.empty()) {
        int y = que.top().second.first;
        int x = que.top().second.second;
        int h = que.top().first * -1;
        que.pop();
 
        if (h <= visit[y][x]) {
            for (int i = 0; i < 8; i++) {
                int nexty = y + dy[i];
                int nextx = x + dx[i];
 
                int newh = (h > height[nexty][nextx]) ? h : height[nexty][nextx];
 
                if (nexty >= 0 && nexty < n && nextx >= 0 && nextx < n) {
                    if (map[nexty][nextx] == 1 && newh < visit[nexty][nextx]) {
                        visit[nexty][nextx] = newh;
                        que.push(make_pair(newh * -1, make_pair(nexty, nextx)));
                    }
                }
            }
        }
    }
 
    int mx = 0;
    for (int i = 0; i < sz; i++) {
        if (visit[point[i].y][point[i].x] > mx)    mx = visit[point[i].y][point[i].x];
        if (visit[point[i].y][point[i].x] == 0)    return 0;
    }
 
    if (mx - num < ans)    ans = mx - num;
 
    return 1;
}
 
void solve()
{
    int mn = 1e9, mx = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (inputMap[i][j] == 'P') {
                starty = i;
                startx = j;
            }
            else if (inputMap[i][j] == 'K') {
                point[sz].y = i;
                point[sz].x = j;
                sz++;
            }
 
            if (height[i][j] < mn)    mn = height[i][j];
            if (height[i][j] > mx)    mx = height[i][j];
        }
    }
 
    sort(range, range + n * n);
 
    int cnt = 1;
    for (int i = 1; i < n * n; i++) {
        if (range[i - 1] != range[i])        range[cnt++] = range[i];
    }
 
    int s = 0, e = cnt - 1;
    int m;
 
    while (s <= e) {
        m = (s + e) / 2;
 
        if (dijkstra(range[m]))    s = m + 1;
        else                       e = m - 1;
    }
 
    for (int i = 0; i <= e; i++) {
        dijkstra(range[i]);
    }
    printf("%d\n", ans);
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%s", inputMap[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &height[i][j]);
            range[i * n + j] = height[i][j];
        }
    }
 
    solve();
 
    return 0;
}

2. dfs + 이진탐색

 이제까지 이진탐색을 해본 것 중 새로운 방식이었다.

최소-최대 고도는 입력받은 값 중에 하나로, 이를 자벌레 마냥 늘리고 줄여가며 피로도의 최소값을 찾는 방식이다.

배달을 완수할 수 있는지는 dfs로 탐색하면서 만나는 K의 개수가 전체 K의 개수와 동일하면 배달을 완수할 수 있다는 지표로 삼았다.

시작, 끝을 가장 작은 고도 값으로 시작하여

배달을 할 수 있으면 시작++하여 피로도를 줄였고, 배달을 할 수 없으면 (끝++)끝값을 증가시켜 배달하는 경로의 고도 범위를 늘려주었다.

이렇게 배달 범위를 늘려갈 수 있는 이유는

어떠한 시작 - 끝 범위에서 배달이 가능하다면 그 끝값 이후의 더 큰값을 끝으로 정해도 무조건 가능하기 때문이다.

-> 128ms

솔직히 무슨 설명을 하는건지 모르겠네...

#include <cstdio>
#include <algorithm>
using namespace std;
 
int n;
char inputMap[55][55];
int height[55][55];
int range[2600];
int visit[55][55];
int ans = 1e9;
int dy[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };
int dx[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
 
int dfs(int y, int x, int s, int e) {
    int res = 0;
 
    if (height[y][x] < s || height[y][x] > e)    return 0;
    if (inputMap[y][x] == 'K')                        
        res = 1;
 
    for (int i = 0; i < 8; i++) {
        int nexty = y + dy[i];
        int nextx = x + dx[i];
 
        if (nexty >= 0 && nexty < n && nextx >= 0 && nextx < n) {
            if (visit[nexty][nextx] == 0) {
                visit[nexty][nextx] = 1;
                res += dfs(nexty, nextx, s, e);
            }
        }
    }
    return res;
}
 
void solve()
{
    int sz = 0;
    int starty, startx;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (inputMap[i][j] == 'P') {
                starty = i;
                startx = j;
            }
            if (inputMap[i][j] == 'K')    sz++;
        }
    }
 
    sort(range, range + n * n);
 
    int cnt = 1;
    for (int i = 1; i < n * n; i++) {
        if (range[i - 1] != range[i])        range[cnt++] = range[i];
    }
    
    int s = 0, e = 0;
    while (e < cnt) {
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visit[i][j] = 0;
            }
        }
 
        visit[starty][startx] = 1;
        if(dfs(starty, startx, range[s], range[e]) == sz) {
            if (range[e] - range[s] < ans)    ans = range[e] - range[s];
            s++;
        }
        else    e++;
    }
 
    printf("%d\n", ans);
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%s", inputMap[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &height[i][j]);
            range[i * n + j] = height[i][j];
        }
    }
 
    solve();
 
    return 0;
}