[SWEA] 1949.등산로 조성 (java) / DFS

@DFS / 40m

최근 너무 어려운 시뮬레이션 문제들만 풀어서 이것도 어렵겠거니 겁먹고 풀었는데

엄청 쉬워서 약간 이게 끝인가..? 놓친거 있는거 아닌가..? 이러면서 풀었다.

행-복

 

 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

 

 

#

구현 포인트

깎을 수 있는 횟수를 매개변수로 들고다니면서

횟수가 남아있다면, 이동하다가 막힐 때(가려는 곳이 이전 높이와 같거나 클 때) 깎고 이동하는 것이다.

 

if (깎을 수 없을 경우) {

     if (지금까지 깎은 횟수 == 0) {

            if (이전 높이 > 가려는 곳 - 최대 깎을 수 있는 크기 K) {

                    dfs(~, 깎은횟수 + 1);

            }

      }

} else {

      안깎고 dfs(~, 깎은 횟수 그대로);

}

 

이 때, 최대한 덜 깎는게 좋다.(왜냐하면 많이 깎아버리면 다음에 큰 수가 나왔을 때 거기로는 갈 수 없으니)

그래서 만약 깎을 수 있다면, 지금 높이 - 1 이 되게 깎는다.

 

이 부분만 잘 구현하면 아주아주 쉬운 문제였다!

 

 

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

public class Solution {
	
	private static int N, K, maxLength, maxHeight, map[][];
	private static boolean[][] visit;
	private static int[] dx = {0, -1, 0, 1}, dy = {1, 0, -1, 0};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			maxLength = maxHeight = 0;
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			visit = new boolean[N][N];
			
			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 (maxHeight < map[i][j])
						maxHeight = map[i][j];
				}
			}
			startPoint();
			sb.append("#" + t + " " + maxLength + "\n");
		}
		System.out.println(sb);
	}

	private static void startPoint() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == maxHeight) {
					visit[i][j] = true;
					dfs(i, j, maxHeight, 1, 0);
					visit[i][j] = false;
				}
			}
		}
	}

	private static void dfs(int x, int y, int height, int length, int shaveCount) {
		for (int d = 0; d < 4; d++) {
			if (maxLength < length) maxLength = length;
			
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if (nx < 0 || nx >= N || ny < 0 || ny >= N || visit[nx][ny]) continue;
			
			if (height <= map[nx][ny]) {			//원래는 이동 불가능하지만 
				if (shaveCount == 0) {				//아직 깎을 수 있고 	
					if (height > map[nx][ny] - K) {	//깎았을 때 지금보다 작아지면 
						visit[nx][ny] = true;
						dfs(nx, ny, height - 1, length + 1, shaveCount + 1);
						visit[nx][ny] = false;
					}
				}
				
			} else {								//원래도 이동 가능했으면 
				visit[nx][ny] = true;
				dfs(nx, ny, map[nx][ny], length + 1, shaveCount);
				visit[nx][ny] = false;
			}
		}
	}
}

 

 

요새 시뮬레이션 풀 때 디버깅때문에 너무 힘들었는데,

오랜만에 편한 문제였다.

근데 DFS 문제를 너무 오랜만에 풀어서 어떻게 하는지 까먹어서 예전 코드 열어보고 풀었다..

 

끝!