개요

dfs로 조건처리를 해주는 문제
풀이방식은 여러가지가 될 수 있다.

1. dfs를 이용한 풀이, 재귀 과정에서 조건을 처리해주는 방법이다
2. 미리 땅을 파놓고 dfs를 돌리는 풀이. 이 방법이 오히려 더 낯설었다 난..

문제분석

등산로를 만드는 규칙은 다음과 같다.

1. 등산로는 가장 높은 봉우리에서 시작해야 한다.

2. 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
   즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

3. 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

가장 중요한 조건들을 볼드처리해놓았다.

첫번째로 할 일은, 가장 높은 봉우리이다. 가장 높은 봉우리는 하나가 아니며,여러개 일 수 있다.

두번째로 할 일은,반드시 높은 지형 -> 낮은 지형으로 연결되어야 한다는 것이다. 즉, 같은 높이 지형으로 가려면, 한번 깎아야 한다는 것이다.

마지막으로 할 일은 최대 K 깊이만큼 지형을 깎아야 한다. 이 공사는 단 한번만 할 수 있다!

문제의 구현을 쭈욱 읊어보자.

1. 가장 높은 봉우리를 찾는다. 이는 여러개일 수 있으니 관리가 필요하다.
2. 어떤 봉우리에서 시작할지 모르기 때문에 모든 봉우리를 탐색하며 해당 봉우리에서 만들 수 있는 모든 길을 탐색한다.
3. 길을 탐색하는 과정에서 공사를 했는지 여부에 따라서 다른 재귀를 탈 수 있도록 해주어야한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * @see
 * @since 11/27/23
 **/
public class 등산로다시풀기 {
	static class Point{
		int x,y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int T,N,K;
	static int max,answer; // 가장 높은 높이
	static Queue<Point> que;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		T = Integer.parseInt(br.readLine());

		for(int t=1;t<T+1;t++){
			st = new StringTokenizer(br.readLine()," ");

			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			max = answer = Integer.MIN_VALUE;

			map = new int[N][N];
			que = new ArrayDeque<>();

			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(max < map[i][j]){
						max = map[i][j];
						que = new ArrayDeque<>(); // 큐를 한번 초기화 한다음
						que.add(new Point(i,j));
					}else if(max == map[i][j]){
						que.add(new Point(i,j));
					}
				}
			}
			while(!que.isEmpty()){
				Point start = que.poll();
				visited = new boolean[N][N];
				visited[start.x][start.y] = true;
				dfs(start,1,false);
			}
			System.out.printf("#%d %d\n",t,answer);
		}
	}
	static void dfs(Point start,int depth,boolean cut){
		if(depth > answer){
			answer = depth;
		}
		for(int i=0;i<4;i++){
			int nx = start.x + dx[i];
			int ny = start.y + dy[i];

			if(nx < 0 || ny < 0 || nx >= N || ny >= N ) continue;
			if(visited[nx][ny]) continue;

			if(map[start.x][start.y] > map[nx][ny]) {
				visited[nx][ny] = true;
				dfs(new Point(nx,ny),depth+1,cut);
				visited[nx][ny] = false; // 다른 케이스를 찾으러 갑니다
			}
			// 현재 높이보다 낮은 곳으로 가면 그냥 간다
			else {
				// 현재 높이와 같거나 높을 경우
				if(!cut && map[nx][ny] - map[start.x][start.y] < K){
					// 한번도 자른적이 없고
					// 잘라서 커버가 가능 한 경우
					visited[nx][ny] = true;
					int height = map[nx][ny];
					map[nx][ny] = map[start.x][start.y] - 1; // 최소한으로 잘라서 유지한다
					dfs(new Point(nx,ny),depth+1,!cut);
					map[nx][ny] = height;
					visited[nx][ny] = false;
				}
			}

		}
	}
}

내가 부가적으로 헷갈렸던 내용을 조금 설명하자면,

if(!cut && map[nx][ny] - map[start.x][start.y] < K)

왜 차이가 K와 같은 것은 안되냐 생각 할 수 있다.
이걸 직접 경우를 만들어서 생각해보면 쉽게 이해가 된다.

K = 2 이면서

7 -> 9로 가려고 한다. 이때 9를 6으로 만들어줘야한다. 왜냐하면 가장 최적의 길이 나오기 위해서는 길을 이전 길보다 1 작게 만드는 것이기 때문이다 (왜냐하면 앞으로 나올 수 중에 가장 큰 수를 가져야,다음에 나올 수 있는 수가 많아지니까!)
어찌되었든, 6이 나올려면 최소 K값이 3은 되어야 한다. 그렇기 때문에 같거나 작으면 안되는 것이다.