1949. 등산로 조성

1949. 등산로 조성

문제 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

DFS로 풀었어요.

문제는 어려워 보였는데,

막상 푸니깐 넘나 쉬었쥬?

역시나 문제 이해하는게 제일 중요합니다.

문제가 어려워 보인다 -> 조건이 많다(복잡하다) -> 문제 리딩 꼼꼼하게!

2018년 4월 12일 - 다듬지 않은 코드 (소요시간 39분) package sw; import java.util.Scanner; public class Q1949 { static int mapSize, k, maxValue, result; static int[][] map; static boolean[][] isVisitMap; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 1; i <= testCase; i++) { mapSize = sc.nextInt(); k = sc.nextInt(); result = 0; maxValue = 0; map = new int[mapSize][mapSize]; isVisitMap = new boolean[mapSize][mapSize]; for (int j = 0; j < mapSize; j++) { for (int k = 0; k < mapSize; k++) { int value = sc.nextInt(); map[j][k] = value; if (value > maxValue) { maxValue = value; } } } solution(); System.out.println("#" + i + " " + result); } } static void solution() { //제일 높은 위치 받아오기 int[][] maxPositions = getMaxPosition(); for (int i = 0; i < maxPositions.length; i++) { int y = maxPositions[i][0]; int x = maxPositions[i][1]; isVisitMap[y][x] = true; // System.out.println("시작"); searchRoute(y, x, map[y][x], 1, false); isVisitMap[y][x] = false; } //해당 위치에서 부터 DFS 시작 } static int[][] getMaxPosition() { int[][] maxPositions = new int[mapSize*mapSize][2]; int num = 0; for (int i = 0; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { if (map[i][j] == maxValue) { maxPositions[num][0] = i; maxPositions[num][1] = j; num += 1; } } } int[][] result = new int[num][2]; for (int i = 0; i < num; i++) { result[i][0] = maxPositions[i][0]; result[i][1] = maxPositions[i][1]; // System.out.println(result[i][0] + " / " + result[i][1]); } return result; } static int[] moveY = {-1, +1, 0, 0}; static int[] moveX = {0, 0, -1, +1}; static void searchRoute(int nowY, int nowX, int nowLevel, int count, boolean isCut) { // System.out.println(nowY + ", " + nowX); if (result < count) { result = count; } for (int i = 0; i < 4; i++) { int tempY = nowY+moveY[i], tempX = nowX+moveX[i]; if (0 <= tempY && tempY < mapSize && 0 <= tempX && tempX < mapSize && !isVisitMap[tempY][tempX]) { int nextLevel = map[tempY][tempX]; if (nowLevel > map[tempY][tempX]) { //안 깍고 갈 수 있는 곳 isVisitMap[tempY][tempX] = true; searchRoute(tempY, tempX, map[tempY][tempX], count+1, isCut); isVisitMap[tempY][tempX] = false; } else if (!isCut && nextLevel-k < nowLevel) { //깍고 갈 수 있는 곳 isVisitMap[tempY][tempX] = true; searchRoute(tempY, tempX, nowLevel-1, count+1, true); isVisitMap[tempY][tempX] = false; } } } } }

2018년 4월 13일 - 다듬은 코드 import java.util.Scanner; public class Q1949 { static int mapSize, k, maxValue, result; static int[][] map; static boolean[][] isVisitMap; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 1; i <= testCase; i++) { result = 0; maxValue = 0; mapSize = sc.nextInt(); k = sc.nextInt(); map = new int[mapSize][mapSize]; for (int j = 0; j < mapSize; j++) { for (int k = 0; k < mapSize; k++) { int value = sc.nextInt(); map[j][k] = value; if (value > maxValue) { maxValue = value; } } } solution(); System.out.println("#" + i + " " + result); } } static void solution() { //제일 높은 위치 받아오기 int[][] maxPositions = getMaxPosition(); //제일 높은 위치에서 부터 DFS 시작 isVisitMap = new boolean[mapSize][mapSize]; for (int i = 0; i < maxPositions.length; i++) { int y = maxPositions[i][0]; int x = maxPositions[i][1]; isVisitMap[y][x] = true; searchRoute(y, x, map[y][x], 1, false); isVisitMap[y][x] = false; } } static int[][] getMaxPosition() { int num = 0; int[][] maxPositions = new int[mapSize*mapSize][2]; for (int i = 0; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { if (map[i][j] == maxValue) { maxPositions[num][0] = i; maxPositions[num][1] = j; num += 1; } } } int[][] result = new int[num][2]; for (int i = 0; i < num; i++) { result[i] = maxPositions[i]; } return result; } static int[] moveY = {-1, +1, 0, 0}; //상,하,좌,우 static int[] moveX = {0, 0, -1, +1}; static void searchRoute(int nowY, int nowX, int nowLevel, int count, boolean isCut) { if (result < count) { result = count; } for (int i = 0; i < 4; i++) { int tempY = nowY+moveY[i], tempX = nowX+moveX[i]; if (0 <= tempY && tempY < mapSize && 0 <= tempX && tempX < mapSize && !isVisitMap[tempY][tempX]) { int nextLevel = map[tempY][tempX]; if (nowLevel > nextLevel) { //안 깍고 갈 수 있는 곳 isVisitMap[tempY][tempX] = true; searchRoute(tempY, tempX, nextLevel, count+1, isCut); isVisitMap[tempY][tempX] = false; } else if (!isCut && nextLevel-k < nowLevel) { //깍아야만 갈 수 있는 곳 isVisitMap[tempY][tempX] = true; searchRoute(tempY, tempX, nowLevel-1, count+1, true); isVisitMap[tempY][tempX] = false; } } } } }