SWEA 1949: 등산로 조성

1. 가장 높은 위치를 찾아서 큐에 넣는다

2. 큐에 넣은 위치를 시작점으로 하는 dfs를 돌려 등산로 길이 중 max값을 찾도록 한다.

   - dfs를 돌릴때에는 공사를 하는 경우/ 안하는 경우를 나눈다.

   - 공사를 하는 경우에는 최소 값만 깎도록 해야 선택 폭이 넓어짐

import java.util.*;
class Solution {
	public static int dr[] = { 0, 1, 0, -1 };
	public static int dc[] = { 1, 0, -1, 0 };
	public static int maxAnswer;

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int test = in.nextInt();
		for (int t = 1; t <= test; t++) {
			int n = in.nextInt();
			int depth = in.nextInt();
			int[][] mat = new int[n][n];
			int max = 0;
			maxAnswer = 0;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					mat[i][j] = in.nextInt();
					max = Math.max(max, mat[i][j]);
				}
			}

			Queue<Position> queue = new LinkedList<Position>();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (mat[i][j] == max) {
						queue.add(new Position(i, j));
					}
				}
			}

			while (!queue.isEmpty()) {
				boolean[][] isVisited = new boolean[n][n];

				Position now = queue.poll();

				isVisited[now.row][now.col] = true;
				dfs(now.row, now.col, depth, 1, 0, mat, isVisited, n);
			}
			System.out.println("#" + t + " " + maxAnswer);
		}

	}

	public static void dfs(int row, int col, int depth, int length, int minus, int[][] mat, boolean[][] isVisited,
			int n) {
		for (int i = 0; i < 4; i++) {
			maxAnswer = Math.max(maxAnswer, length);

			int newRow = row + dr[i];
			int newCol = col + dc[i];

			if (isBoundary(newRow, newCol, n) && !isVisited[newRow][newCol]) {
				// 깎는경우
				if (mat[row][col] <= mat[newRow][newCol] && mat[row][col] > mat[newRow][newCol] - depth) {
					isVisited[newRow][newCol] = true;
					dfs(newRow, newCol, 0, length + 1, mat[newRow][newCol] - mat[row][col] + 1, mat, isVisited, n);
					isVisited[newRow][newCol] = false;
				}
				// 안깎는경우
				else if (mat[row][col] - minus > mat[newRow][newCol]) {
					isVisited[newRow][newCol] = true;
					dfs(newRow, newCol, depth, length + 1, 0, mat, isVisited, n);
					isVisited[newRow][newCol] = false;
				}
			}
		}
	}

	public static boolean isBoundary(int row, int col, int N) {
		if (row < 0) {
			return false;
		}
		if (col < 0) {
			return false;
		}
		if (row >= N) {
			return false;
		}
		if (col >= N) {
			return false;
		}
		return true;
	}
}

class Position {
	int row;
	int col;

	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}
}