[문제해결을 위한 창의적 알고리즘] 암벽등반 (고급, p225)

이 문제 역시 이분 탐색을 이용한 결정 문제이다. 문제에서 3/4이상을 지나다녀야 한다는 제약 조건이 있는데, 이를 위해 모든 지점에서 모두 출발해 보며 확인할 것이 아니라, 1/4을 초과한 지점만 확인해 보면 된다는 아이디어가 더해져 더 빠르게 수행할 수 있도록 푸는 방법을 적용해 보았다.

import java.util.Scanner;

public class ClimbingSol231 {

public static int N;

// N이 500까지 이므로 500으로 선언

public static int[][] M = new int[500][500];

public static boolean[][] chk= new boolean[500][500];

// 상,하,좌,우 탐색 방향 설정

public static int[] dx = new int[]{0,1,0,-1};

public static int[] dy = new int[]{1,0,-1,0};

public static int lb, ub, m;

public static int max(int a, int b) {

return a > b ? a : b;

}

public static int abs(int a){

return a > 0 ? a : -a;

}

// a, b 좌표가 탐색할 수 있는 것인지 확인

public static boolean can(int a, int b){

return (0<=a && a<N) && (0<=b && b < N);

}

public static int dfs(int a, int b, int h){

int area = 1;

chk[a][b]=true;

for (int i = 0; i < 4; i++)

if (can(a+dx[i], b+dy[i]) && !chk[a+dx[i]][b+dy[i]] &&

abs(M[a][b]-M[a+dx[i]][b+dy[i]])<=h)

area+=dfs(a+dx[i],b+dy[i],h);

return area;

}

// 3/4를 채우려면 최소 1/4초과하는 영역에서만 출발해 보면 됨

public static boolean f(int h){

int mcnt=0, cnt;

for (int i =0; i< N/2+1; i++)

for (int j = 0; j < N/2+1; j++)

if (!chk[i][j]){

cnt = dfs(i, j, h);

mcnt = max(cnt, mcnt);

}

return (mcnt >= (int)(N*N*0.75));

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

N = sc.nextInt();

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++){

M[i][j]=sc.nextInt();

ub = max(ub, M[i][j]);

}

sc.close();

while (lb<ub){

for (int i = 0; i < 511; i++)

for (int j = 0; j < 511; j++)

chk[i][j]=false;

m = (lb+ub+1)/2;

if (f(m))

ub = m;

else

lb=m+1;

}

System.out.println(ub);

return;

}

}

Big O(N^4): N^2위치에서 출발해서 N^2을 돌아다니며 결과 확인

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/ClimbingSol231.java

문제해결을 위한 창의적 알고리즘 목록