[SWEA] JAVA - 1949. [모의 SW 역량테스트] 등산로 조성

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

SW Expert Academy

생각

가장 높은 봉우리에서부터 시작하여 가장 긴 경로를 찾는 문제입니다.

등산로를 만들때 현재위치보다 다음위치가 더 낮아야 등산로를 만들 수 있습니다. 이때 최장 등산로를 만들기 위해서 최대 K 값만큼 봉우리를 깎을 수 있지만 단 한번만 깎을 수 있습니다.

 

모든 경우를 탐색해야 하기 때문에 DFS 를 사용하여 완전탐색으로 문제를 풀었습니다.
제가 만든 재귀함수의 정의는 다음과 같습니다.

solve(int y, int x, int k, int length, int height) -> k : 내가 깎아본 횟수 카운트, length : 현재까지 만든 등산로 길이, height : 현재 등산로 높이 값

 

1. 가장 높은 봉우리에서 시작하는 dfs 탐색을 시작합니다. 

2. 다음 봉우리의 높이가 지금보다 낮으면, 깎아보는 걸 시도하지 않고 다음 단계를 정하기 위해 재귀함수를 호출합니다.

3. 다음 봉우리의 높이가 지금보다 크거나 똑같고, 한번도 깎아보는걸 시도하지 않았다면 깎아봅니다. 이때 최소 높이인 1만큼만 깎아야 최장길이가 나올 확률이 높아지기 때문입니다. (1부터 K만큼 모두 깎아보는 모든 경우를 탐색할 수 있지만 한번 더 생각해보면 그럴 필요가 없습니다.)

4. 가장 긴 등산로의 길이를 찾아서 출력합니다.

 

 

(참고) 처음에 map[ny][nx]-=1 과 같은 방식으로 문제를 풀었는데 테스트케이스가 32개만 맞아서 직접적으로 상태배열값을 수정하면 안되는건가라고 생각했습니다..ㅎ map[ny][nx]는 현재 위치의 높이에서 1을 빼줘야했었습니다. 실수했네요ㅎㅎ

if(k == 0) {
	if(map[ny][nx]-K < map[y][x]) {
		int prev = map[ny][nx];
		map[ny][nx] = map[y][x]-1; // 1만 깎아주고
		visited[ny][nx] = true;

		solve(ny, nx, k+1, length+1);
		map[ny][nx] = prev;//다시 원복
		visited[ny][nx] = false;
						
	}

}

 

Java Code 1 - 파라미터로 높이값 넘겨주는 방식 (상태배열 값 수정하지 않음)

package com.java.algorithm;

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

public class SWEA_1949_등산로조성 {
	static int N,K;
	static Queue<int[]> start;
	static int[][] map;
	static boolean[][] visited;
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,1,-1};
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		int TC = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= TC; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			map = new int[N][N];
			
			
			start = new LinkedList<int[]>();
			
			int maxHeight = Integer.MIN_VALUE;
			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());
					maxHeight = Math.max(maxHeight, map[i][j]);
				}
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(maxHeight == map[i][j]) {
						start.add(new int[] {i,j});
					}
				}
			}
			
			ans = 0;
			while(!start.isEmpty()) {
				int[] now = start.poll();
				visited = new boolean[N][N];
				visited[now[0]][now[1]] = true;
				solve(now[0], now[1], 0, 1, map[now[0]][now[1]]);
			}
			sb.append("#").append(t).append(" ").append(ans).append("\n");
			
		}
		System.out.print(sb);
	}
	
	private static void solve(int y, int x, int k, int length, int height) {
		if(ans < length) {
			ans = length;
		}
		
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if(ny >= N || ny < 0 || nx >= N || nx < 0 || visited[ny][nx]) continue;
			//1. 다음위치가 지금보다 낮으면, k사용하지 않고 다음단계로 들어간다.
			//2. 다음위치가 지금보다 크거나 똑같고, 한번도 안깎아봤으면 깎아본다. -> 최소로 깎아야 최장길이가 나올 확률 상승
			if(map[ny][nx] < height) {
				visited[ny][nx] = true;
				solve(ny, nx, k, length+1, map[ny][nx]);
				visited[ny][nx] = false;
			}
			else{
				if(k == 0) {
					if(map[ny][nx]-K < height) {
						visited[ny][nx] = true;
						solve(ny, nx, k+1, length+1, height-1);
						visited[ny][nx] = false;
						
					}

				}
			}

			

		}
	}

}

Java Code2 - 상태배열 값 수정하는 방식

package com.java.algorithm;

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

public class SWEA_1949_등산로조성 {
	static int N,K;
	static Queue<int[]> start;
	static int[][] map;
	static boolean[][] visited;
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,1,-1};
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		int TC = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= TC; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			map = new int[N][N];
			
			
			start = new LinkedList<int[]>();
			
			int maxHeight = Integer.MIN_VALUE;
			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());
					maxHeight = Math.max(maxHeight, map[i][j]);
				}
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(maxHeight == map[i][j]) {
						start.add(new int[] {i,j});
					}
				}
			}
			
			ans = 0;
			while(!start.isEmpty()) {
				int[] now = start.poll();
				visited = new boolean[N][N];
				visited[now[0]][now[1]] = true;
				solve(now[0], now[1], 0, 1);
			}
			sb.append("#").append(t).append(" ").append(ans).append("\n");
			
		}
		System.out.print(sb);
	}
	
	private static void solve(int y, int x, int k, int length) {
		if(ans < length) {
			
			ans = length;
		}
		
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if(ny >= N || ny < 0 || nx >= N || nx < 0 || visited[ny][nx]) continue;
			//1. 다음위치가 지금보다 낮으면, k사용하지 않고 다음단계로 들어간다.
			//2. 다음위치가 지금보다 크거나 똑같고, 한번도 안깎아봤으면 깎아본다. -> 최소로 깎아야 최장길이가 나올 확률 상승
			if(map[ny][nx] < map[y][x]) {
				visited[ny][nx] = true;
				solve(ny, nx, k, length+1);
				visited[ny][nx] = false;
			}
			else{
				if(k == 0) {
					if(map[ny][nx]-K < map[y][x]) {
						int prev = map[ny][nx];
						map[ny][nx] = map[y][x]-1; // 1만 깎아주고
						visited[ny][nx] = true;
						
						solve(ny, nx, k+1, length+1);
						map[ny][nx] = prev;//다시 원복
						visited[ny][nx] = false;
						
					}

				}
			}

			

		}
	}

}