문제 링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq
문제
등산로를 조성하려고 한다.등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.
등산로를 만드는 규칙은 다음과 같다.
① 등산로는 가장 높은 봉우리에서 시작해야 한다.
② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.
③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.
N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.
이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.
[예시]
위 [Fig. 1]과 같이 N = 5인 지도가 주어진 경우를 살펴보자.
가장 높은 봉우리는 높이가 9로 표시된 세 군데이다.
이 세 곳에서 출발하는 가장 긴 등산로 중 하나는 아래 [Fig. 2]와 같고, 이 때 길이는 5가 된다.
만약 최대 공사 가능 깊이 K = 1로 주어질 경우,
아래 [Fig. 3]과 같이 빨간색 부분의 높이를 9에서 8로 깎으면 길이가 6인 등산로를 만들 수 있다.
이 예에서 만들 수 있는 가장 긴 등산로는 위와 같으며, 출력할 정답은 6이 된다.
[제약 사항]
1. 시간 제한 : 최대 51개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
2. 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
3. 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
4. 지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.
5. 지도에서 가장 높은 봉우리는 최대 5개이다.
6. 지형은 정수 단위로만 깎을 수 있다.
7. 필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.
[입력]
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.
그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.
[출력]
테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.
문제 분석
- 최대한 긴 등산로를 만들고자 한다
- 각 숫자는 지형의 높이
- 가장 높은 봉우리에서 시작 → 가로or세로 인접한 자신보다 낮은 봉우리로만 연결 가능
- 딱 한 곳 막히는 부분(높거나 같은 봉우리)을 최대 K만큼 깎을 수 있음
- 필요한 경우 지형을 깎아 높이를 0으로 만들 수 있음
⇒ 4방 그래프에서 최장거리 구하기
풀이 방법
- 가장 높은 봉우리 리스트에 저장
- 리스트에 있는 최고봉 한 개씩 DFS 돌려서 가장 긴 등산로 max 값 저장
- DFS를 쓴 이유 : 공사를 했다가 안했다가 하는 백트래킹 과정이 필요하기 때문에
- 현재 봉우리보다 다음 봉우리가 낮을 때 다음 재귀
- else 봉우리가 높거나 같지만, 아직 깎은 적이 없고, 깎았을 때 갈 수 있다면(다음 봉우리-K<현재 봉우리) 다음 봉우리 = 현재 봉우리-1, 다음 재귀
- 시간복잡도 : 5(최고봉개수)*4*N(최대8)^4 = 81,920
코드
package week7_2209_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;
public class Solution_1949_등산로조성{
static int N,K;
static int[][] map;
static List<int[]> high;
static int max;
static int[][] delta = {{0,1},{0,-1},{1,0},{-1,0}};
static boolean[][] visited;
static boolean isCut;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("C:\\Users\\SSAFY\\Downloads\\sample_input (4).txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for(int test_case=1; test_case<=T; test_case++) {
max = 0;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //지도 한변의 크기
K = Integer.parseInt(st.nextToken()); //최대 공사 가능 깊이
map = new int[N][N];
int maxHeight = 0;
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]>maxHeight) {
maxHeight = map[i][j];
high = new ArrayList<>();
}
if(map[i][j]==maxHeight) high.add(new int[] {i,j});
}
}
for(int[] h : high) {
visited = new boolean[N][N];
isCut = false;
visited[h[0]][h[1]] = true;
dfs(maxHeight, h[0], h[1], 1);
}
System.out.println("#"+test_case+" "+max);
}
}
static void dfs(int height, int r, int c, int length) {
for(int[] d : delta) {
int tr = r+d[0];
int tc = c+d[1];
if(0<=tr && tr<N && 0<=tc && tc<N && !visited[tr][tc]) {
visited[tr][tc] = true;
int nextHeight = map[tr][tc];
//다음 봉우리가 더 작은 경우
if(nextHeight<height) dfs(nextHeight, tr,tc,length+1);
//다음 봉우리가 같거나 크지만, 깎을 수 있는 경우
else if(!isCut && nextHeight>=height && nextHeight-K<height) {
isCut = true;
dfs(height-1, tr,tc, length+1);
isCut = false;
}
visited[tr][tc] = false;
}
}
//더 이상 갈수 있는 곳이 없음
max = Math.max(length, max);
}
}