티스토리 뷰

알고리즘 관련/BOJ

BOJ)5846 Tractor

JASON 자손9319 2017. 10. 24. 16:25

문제: icpc.me/5846


n^2의 격자에서 한 점에서 4방향으로 일정 조건(둘의 차이가 k이하이면 이동 가능)을 만족하면 이동가능할 때

임의의 한점을 잡아 반 이상의 격자를 순회할 수 있는 최소의 k를 찾는 문제이다.


최대중의 최소를 구하는 문제이므로 파라메트릭 서치를 생각해볼 수 있다.

이 때 k를 mid값으로 정해놓은 뒤에 만족 여부를 확인하게 되는데

만족여부는 dfs를 통하여 확인할 수 있다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a[555][555], b[555][555];
int dx[] = { 0,0,1,-};
int dy[] = { 1,-1,0,};
int chk(int x, int y) {
    return <= x&&< n && <= y&&< n;
}
int dfs(int x, int y,int z) {
    b[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (chk(cx, cy) && !b[cx][cy] && abs(a[x][y] - a[cx][cy]) <= z)
            b[x][y] += dfs(cx, cy, z);
    }
    return b[x][y];
}
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            scanf("%d"&a[i][j]);
    }
    int lo = 0;
    int hi = 1e6 + 1;
    while (lo < hi) {
        memset(b, 0sizeof(b));
        int mid = (lo + hi) >> 1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!b[i][j])
                    ans = max(ans, dfs(i, j, mid));
            }
        }
        if (ans >= (n*n) / 2)
            hi = mid;
        else
            lo = mid + 1;
    }
    printf("%d\n", lo);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14195 DotB  (0) 2017.11.15
BOJ)14748 Flow Graph Complexity  (0) 2017.10.24
BOJ)5846 Tractor  (0) 2017.10.24
BOJ)5849 Cow Crossings  (0) 2017.10.24
BOJ)2023 신기한 소수  (0) 2017.10.16
BOJ)13212 Random  (0) 2017.10.16
댓글
댓글쓰기 폼