코드 복사/붙여넣기 하는 당신이 아름답습니다.

2842 : 집배원 한상덕

풀이

parametric search로도 풀릴 것 같은데

나는 투포인터로 풀었다.

높이가 될 수 있는 후보는 1000000개이지만

주어지는 그리드의 크기가 50*50이 최대이므로 많아야 2500개 후보가 있을 수 있다.

주어진 높이들을 정렬한 다음, 투포인터로 구간을 잡아 dfs를 돌려주자.

코드

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

const int dx[] = { 0,0,-1,1,-1,-1,1,1 };
const int dy[] = { -1,1,0,0,-1,1,-1,1 };

int n, sx, sy, k, b[55][55], chk[55][55];
char a[55][55];
vector<int> v;

int dfs(int x, int y, int mn, int mx) {
    if (chk[x][y] ||
        b[x][y] < mn || mx < b[x][y] ||
        x < 1 || n < x || y < 1 || n < y) {
        return 0;
    }
    chk[x][y] = 1;
    int ret = 0;
    if (a[x][y] == 'K') {
        ret++;
    }
    for (int i = 0; i < 8; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        ret += dfs(nx, ny, mn, mx);
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", a[i]+1);
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 'P') {
                sx = i, sy = j;
            }
            if (a[i][j] == 'K') {
                k++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &b[i][j]);
            v.push_back(b[i][j]);
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int i, j = 0, ans = 1e9;
    for (i = 0; i < v.size(); i++) {
        while (1) {
            memset(chk, 0, sizeof(chk));
            if (dfs(sx, sy, v[j], v[i]) != k) {
                break;
            }
            ans = min(ans, v[i]-v[j]);
            j++;
        }
    }

    printf("%d", ans);

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-11-19 13:57

Read more posts by this author