문제
등산로를 조성하려고 한다.
등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.
등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.
등산로를 만드는 규칙은 다음과 같다.
① 등산로는 가장 높은 봉우리에서 시작해야 한다.
② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.
③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.
N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.
이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.
[예시]
위 [Fig. 1]과 같이 N = 5인 지도가 주어진 경우를 살펴보자.
가장 높은 봉우리는 높이가 9로 표시된 세 군데이다.
이 세 곳에서 출발하는 가장 긴 등산로 중 하나는 아래 [Fig. 2]와 같고, 이 때 길이는 5가 된다.
만약 최대 공사 가능 깊이 K = 1로 주어질 경우,
아래 [Fig. 3]과 같이 빨간색 부분의 높이를 9에서 8로 깎으면 길이가 6인 등산로를 만들 수 있다.
이 예에서 만들 수 있는 가장 긴 등산로는 위와 같으며, 출력할 정답은 6이 된다.
[제약 사항]
-
시간 제한 : 최대 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부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.
풀이
문제의 핵심은 어떻게 지형을 깍느냐이다
다행이 깍을수 있는 최대 높이 K 와 N 의 최대 크기가 5, 18 로 크지 않다
그리고 지형을 깍지만 무조건 하나만 깍기 때문에 모든 지형을 0 ~ K 만큼깍아 보아도 최악의 경우 18 * 18 * 5 로 1620 이다
그리고 경로를 찾아야하는데 찾을때 현제 경사보다 작은 경사를 골라야한다.
문제에서 가장긴 경로를 찾으라 했고 최단 경로를 구하는게 아니다 경로를 깊게 파고 가야하니 머리속에 dfs 먼저 그려졌다.
dfs 의 시간복잡도는 O (V + E) 로 최악의 경우 모든 지형의 4방향을 탐색함으로 18*18 + 4 = 1296 이다
즉 총 시간복잡도는 1602 * 1296 = 2,076,192 2백만 정도 나오게 된다.
코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
class PointDto {
int r;
int c;
public PointDto(int r, int c) {
super();
this.r = r;
this.c = c;
}
}
public class Solution {
// 단순하게 생각하는 연습
static int Tc;
static int N;
static int K;
static int[][] originMap;
static int maxRoad;
static boolean[][] check;
static int[][] dArr = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Tc = Integer.parseInt(br.readLine());
for (int tc = 0; tc < Tc; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
originMap = new int[N][N];
check = new boolean[N][N];
for (int row = 0; row < N; row++) {
st = new StringTokenizer(br.readLine());
for (int col = 0; col < N; col++) {
originMap[row][col] = Integer.parseInt(st.nextToken());
}
}
// 바꿀거하나선택하는 부분
maxRoad = 0;
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
for (int k = 0; k <= K; k++) {
List<PointDto> maxList = findMax(originMap);
originMap[row][col] -= k;
for(PointDto point : maxList) {
check = new boolean[N][N];
check[point.r][point.c] = true;
dfs(point.r, point.c, 1);
}
originMap[row][col] += k;
}
}
}
System.out.printf("#%d %d\n", tc + 1, maxRoad);
}
}
private static void dfs(int targetRow, int targetCol, int depth) {
maxRoad = Math.max(maxRoad, depth);
for (int d = 0; d < 4; d++) {
int nextRow = targetRow + dArr[d][0];
int nextCol = targetCol + dArr[d][1];
if (isOut(nextRow, nextCol) && !check[nextRow][nextCol]) {
if (originMap[targetRow][targetCol] > originMap[nextRow][nextCol]) {
check[nextRow][nextCol] = true;
dfs(nextRow, nextCol, depth + 1);
check[nextRow][nextCol] = false;
}
}
}
}
private static boolean isOut(int nextRow, int nextCol) {
return nextRow < N && nextRow >= 0 && nextCol < N && nextCol >= 0;
}
private static List<PointDto> findMax(int[][] inputMap) {
int maxNum = 0;
List<PointDto> res = new ArrayList<>();
for (int[] row : inputMap) {
for (int el : row) {
maxNum = Math.max(el, maxNum);
}
}
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (originMap[row][col] == maxNum) {
res.add(new PointDto(row, col));
}
}
}
return res;
}
}
