[BOJ] 2842번: 집배원 한상덕

2842번: 집배원 한상덕

이분 탐색 + flood-fill도 가능하지만 inchworm 알고리즘을 사용할 수도 있다. 피로도와 방문할 수 있는 곳은 비례하기 때문이다. (찾아보니 단조함수이면 가능하다고 한다.)

inchworm 알고리즘에서는 1차원으로 작업을 하는데 고차원에서도 가능한지는 모르겠다만... 아무튼 1차원에서 작업하기 때문에 2차원의 좌표에 있는 값을 1차원의 위치로 바꿔주고 정렬을 한 상태에서 inchworm 알고리즘을 돌면서 flood-fill을 했다.

#include <cstdio>
#include <algorithm>
using namespace std;

const int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, dy[] = { 1, 0, -1, -1, -1, 0, 1, 1 };
int n, vec[2505], height[50][50], sx, sy, s, l, ret = 1e10;
bool vst[50][50];
char m[50][51];

void dfs(int x, int y) {
    if (0 > x || x >= n || 0 > y || y >= n || vst[x][y]) return;
    if (height[x][y] < vec[s] || height[x][y] > vec[l]) return;
    vst[x][y] = true;
    for (int i = 0; i < 8; ++i) dfs(x + dx[i], y + dy[i]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", m[i]);
        for (int j = 0; j < n; ++j) 
            if(m[i][j] == 'P') sx = i, sy = j;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &height[i][j]);
            vec[i * n + j] = height[i][j];
        }
    }
    sort(vec, vec + n * n);
    while (l < n * n) {
        dfs(sx, sy);
        bool flag = false;
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            if (!vst[i][j] && m[i][j] == 'K') flag = true;
            vst[i][j] = false;
        }
        flag ? l++ : ret = min(ret, vec[l] - vec[s++]);
    }
    printf("%d\n", ret);

    return 0;
}