[swea-D4] 25052. [모의 SW 역량테스트] 등산로 조성

# [swea-D4] 25052. [모의 SW 역량테스트] 등산로 조성

🙋‍♂️ 들어가며

조건을 잘 읽어보자

• 등산로는 가장 높은 봉우리에서 시작
• 딱 한곳만 최대 K깊이만큼 지형 깎기

그러면 필요한 것은 다음과 같겠다

• 상태관리를 통해 다음 높이를 수정한 상태에서 dfs 그 이후, 다시 다음 높이 복구
• 방문처리, 자를 수 있는지 여부도 마찬가지다
• 그리고 더이상 지나갈 수 없다고 판단되면 현재 길이를 최대 길이와 비교하여 갱신한다

✅ 코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;



public class Solution {
	static int N, K;
	static int[][] arr;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	static int max_leng;
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc < T+1; tc++) {
			String[] NK = br.readLine().split(" ");
			N = Integer.parseInt(NK[0]);
			K = Integer.parseInt(NK[1]);
			
			// 1-1. 배열 생성
			// 1-2. 등산로는 가장 높은 봉우리에서 시작
			int max_height = 1;
			arr = new int[N][N];
			
			for (int r = 0; r < N; r++) {
				String[] cols = br.readLine().split(" ");
				for (int c = 0; c < N; c++) {
					arr[r][c] = Integer.parseInt(cols[c]);
					// 1-3. 비교 -> 현재 높이, 최고 높이 
					int cur_height = arr[r][c];
					max_height = Math.max(max_height, cur_height);
				}
			}
			
			// 2-1. 등산로 탐색
			max_leng = 1;
			boolean[][] visited = new boolean[N][N];
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < N; c++) {
					// 2-2. 현재 높이
					int cur_height = arr[r][c];
					
					// 2-3-a. 현재 높이 == 최고 높이 일때
					if (cur_height == max_height) {
						int sr = r;
						int sc = c;
						int cur_leng = 1;
						boolean can_cut = true;
						
						// 2-3-b 방문 처리후 dfs
						visited[sr][sc] = true;
						dfs(sr, sc, visited, can_cut, cur_leng);
						
						// 2-3-c dfs 이후 방문 해제
						visited[sr][sc] = false;
					}
				}
			}
			
			// 4. 출력
			System.out.println("#" + tc + " " + max_leng);
		}
	}
	
	
	
	// 3. dfs 함수
	static void dfs(int cr, int cc, boolean[][] visited, boolean can_cut, int cur_leng) {
		
		// 3-1. 더이상 이동 못하면 길이 갱신하고 종료
		boolean can_you_move = false;
		
		for (int d = 0; d < 4; d++) {
			int nr = cr + dr[d];
			int nc = cc + dc[d];
			
			// 3-2. 범위 초과시 skip
			if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
			
			// 3-3. 방문했으면 skip
			if (visited[nr][nc]) continue;
			
			// 3-4. 범위 이내, 미방문일때
			
			// 3-5. 다음 지점이 현재 지점보다 더 낮다면?
			if (arr[nr][nc] < arr[cr][cc]) {
				
				// 3-5-a 방문 처리후 dfs
				visited[nr][nc] = true;
				dfs(nr, nc, visited, can_cut, cur_leng+1);
				can_you_move = true;
				
				// 3-5-b. dfs 이후 방문해제
				visited[nr][nc] = false;
			}
			
			// 3-6. 다음 지점이 현재 지점보다 같거나 높을때
			if (arr[nr][nc] >= arr[cr][cc]) {
				// 3-6-a 꺾을 수 없다면 -> skip
				if (!can_cut) continue;
				
				// 3-6-b 자를 수 있다면?
				if (can_cut) {
					for (int x = 1; x < K+1; x++) {
						int decreased_height = arr[nr][nc] - x;
						// 3-6-c. 낮아진 높이를 갈 수 있다면? -> 다음 좌표 수정
						if (decreased_height < arr[cr][cc]) {
							int original_height = arr[nr][nc];
							arr[nr][nc] = decreased_height;
							visited[nr][nc] = true;
							can_cut = false;
							can_you_move = true;
							dfs(nr, nc, visited, can_cut, cur_leng+1);
							
							// 3-7-d. 방문해제, 다음높이 복구, 자를수 있는지 여부 해제
							visited[nr][nc] = false;
							arr[nr][nc] = original_height;
							can_cut = true;
						}
					}
				}
			}
		}
		
		// 3-7. 더이상 이동 못하면 길이 비교
		if (!can_you_move) {
			max_leng = Math.max(max_leng, cur_leng);
		}
		
		
	}
	
	
}