1949. [모의 SW 역량테스트] 등산로 조성 : JAVA

문제 유형
백트랙킹

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 등산로를 조성하려고 한다.
2. 등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.
3. 등산로는 가장 높은 봉우리에서 시작해야 한다.
4. 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
5. 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.
6. 출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.

가지치기 없는 순수 백트랙킹으로 풀면 시간초과가 날 줄 알았는데, 가지치기를 하지 않아도 통과가 되는 기이한? 문제였습니다.

static void dfs(int r, int c, int flag, int cnt) {


    if (map[r][c] + cnt <= answer) return;

    answer = Math.max(answer, cnt);


    for (int dir = 0; dir < 4; dir++) {
        int nr = r + dr[dir];
        int nc = c + dc[dir];

        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
        if (vis[nr][nc]) continue;
        if (map[r][c] <= map[nr][nc]) {
            if (flag == 0) {
                if (map[r][c] - 1 < map[nr][nc] - k) continue;
                int temp = map[nr][nc];
                vis[nr][nc] = true;
                map[nr][nc] = map[r][c] - 1;
                dfs(nr, nc, 1, cnt + 1);
                map[nr][nc] = temp;
                vis[nr][nc] = false;
            }
        } else {
            vis[nr][nc] = true;
            dfs(nr, nc, flag, cnt + 1);
            vis[nr][nc] = false;
        }
    }
}

위는 핵심 메서드인 dfs입니다.
일반적인 백트랙킹과 다른점은 한 번 등산로를 깎을 수 있다는 점입니다.
flag를 사용해서 설정하여 등산로를 이미 깎았는지의 여부를 저장합니다.
또한 깎은 등산로는 탐색이 종료되면 원상복구해줘야합니다.

if (map[r][c] + cnt <= answer) return;

가지치기가 하나 존재합니다.
만약 현재 등산로의 높이가 5라면 최대 5번 더 이상할 수 있습니다.
만약 현재까지 이동한 횟수와 앞으로 이동할 수 있는 최대 개수를 더해도 answer이하보다 작으면 더 이상 탐색하지 않습니다.

시간 복잡도
O(T * 3^20 * 5)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;


class Node {
	int r;
	int c;
	
	Node (int r, int c) {
		this.r = r;
		this.c = c;
	}
}

public class Main {
	
	static int n,k;
	static int[][] map;
	static boolean[][] vis;
	static int answer = 0;
	static int[] dr = {1,-1,0,0};
	static int[] dc = {0,0,1,-1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int t=1; t<=T; t++) {
			st = new StringTokenizer(br.readLine());
			
			n = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			answer = 0;
			
			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());
					maxHeight = Math.max(maxHeight, map[i][j]);
				}
			}
			
			List<Node> startNodes = new ArrayList<>();
			
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					if (maxHeight == map[i][j]) startNodes.add(new Node(i,j));
				}
			}
			
			for (Node node : startNodes) {
				vis = new boolean[n][n];
				vis[node.r][node.c] = true;
				dfs(node.r, node.c, 0, 1);
				vis[node.r][node.c] = false;
			}
			
			
			sb.append("#").append(t).append(" ").append(answer).append("\n");
			
		}

		
		System.out.println(sb.toString());
		
	}
	
	static void dfs(int r, int c, int flag, int cnt) {
		
		
		if (map[r][c] + cnt <= answer) return;
		
		answer = Math.max(answer, cnt);
		
		
		for (int dir=0; dir<4; dir++) {
			int nr = r + dr[dir];
			int nc = c + dc[dir];
			
			if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
			if (vis[nr][nc]) continue;
			if (map[r][c] <= map[nr][nc]) {
				if (flag == 0) {
					if (map[r][c] - 1 < map[nr][nc] - k) continue;
					int temp = map[nr][nc];
					vis[nr][nc] = true;
					map[nr][nc] = map[r][c] - 1;
					dfs(nr, nc, 1, cnt+1);
					map[nr][nc] = temp;
					vis[nr][nc] = false;
				}
			}
			else {
				vis[nr][nc] = true;
				dfs(nr,nc,flag,cnt+1);
				vis[nr][nc] = false;
			}
		}
	}
}