문제
등산로를 조성하려고 한다.
등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.
등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.
등산로를 만드는 규칙은 다음과 같다.
① 등산로는 가장 높은 봉우리에서 시작해야 한다.
② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.
③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.
N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.
이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.
제약 사항
-
시간 제한 : 최대 51개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
-
지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
-
최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
-
지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.
-
지도에서 가장 높은 봉우리는 최대 5개이다.
-
지형은 정수 단위로만 깎을 수 있다.
-
필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.
입력
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.
그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.
출력
테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.
예제 입력
10
5 1
9 3 2 3 2
6 3 1 7 5
3 4 8 9 9
2 3 7 7 7
7 6 5 5 8
3 2
1 2 1
2 1 2
1 2 1
… 예제 출력
#1 6
#2 3
#3 7
#4 4
#5 2
#6 12
#7 6
#8 7
#9 10
#10 19풀이
이 문제는 DFS 알고리즘을 이용해서 풀 수 있었고 약간의 수학적으로 고민을 해보아야 완벽히 풀 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N;
static int[][] map;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int ans = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
int K = Integer.parseInt(input[1]);
visited = new boolean[N][N];
map = new int[N][N];
ans = 0;
int max = 0;
for(int i=0; i<N; i++) {
input = br.readLine().split(" ");
for(int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(input[j]);
max = Math.max(max, map[i][j]);
}
}
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(map[i][j]==max){
visited = new boolean[N][N];
dfs(i, j, K, 1, map[i][j]);
}
}
}
System.out.println(ans);
}
public static void dfs(int x, int y, int k, int leng, int past) {
int cnt = 0;
visited[x][y] = true;
for(int i=0; i<4; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny] || map[nx][ny]-past+1>k) continue;
if(map[nx][ny]>=past)
dfs(nx, ny, 0, leng+1, past-1);
else
dfs(nx, ny, k, leng+1, map[nx][ny]);
cnt++;
}
visited[x][y] = false;
if(cnt==0)
ans = Math.max(ans, leng);
}
}