[Java] 프로그래머스 118669. 등산코스정하기 (Lv.3)

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

등산코스 정하기 문제입니다.

몇 달이 지났지만 코딩 테스트 당시에도 굉장히 급박하게 풀었던 기억이 나는데요. 

우선 정답으로 통과한 아이디어는 이렇습니다.

 

입구 -> 정상 -> 출발한 입구로 돌아오는 경로의 최대 Intensity를 최소로 만드는 경로를 구해야 합니다. 이는 정상 -> 입구로 가는 경로의 최대 Intensity의 최솟값과 같습니다. (같은 길을 두 번 왕복해도 Intensity는 똑같기 때문입니다.)

N이 5만으로 큰 값이기 때문에 2차원 배열로 만들시 25억 사이즈가 됩니다. 배열 대신 인접리스트로 그래프를 구현하고, 모든 정상에 대해 적절하게 가지치기를 하며 BFS를 돌려 각 입구까지 가는 최대 Intensity의 최소값을 구했습니다.

 

이제 구한 값들을 비교해 정답을 찾아내면 됩니다.

 

굉장히 브루트포스 스럽게 풀었고 가지치기를 잘 한 덕에 모든 테케에 통과는 했지만 효율성이나 구현이 깔끔하지 못합니다.

어차피 Python언어로도 다시 풀 예정이기 때문에 조금 더 다듬어서 Java로도 나은 솔루션을 다시 올리도록 하겠습니다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class q118669_Programmers_등산코스정하기 {
	public static void main(String[] args) {

		int[][] paths = new int[][] { { 1, 2, 3 }, { 2, 3, 5 }, { 2, 4, 2 }, { 2, 5, 4 }, { 3, 4, 4 }, { 4, 5, 3 },
				{ 4, 6, 1 }, { 5, 6, 1 } };
		int[] gates = new int[] { 1, 3 };
		int[] summits = new int[] { 5 };

		System.out.println(Arrays.toString(solution(6, paths, gates, summits)));
	}

	static public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
		int[] answer = { -1, 10_000_001 };

		boolean[] gateCheck = new boolean[n + 1];
		boolean[] summitCheck = new boolean[n + 1];

		for (int i = 0; i < gates.length; i++) {
			gateCheck[gates[i]] = true;
		}
		for (int i = 0; i < summits.length; i++) {
			summitCheck[summits[i]] = true;
		}

		ArrayList<ArrayList> pathList = new ArrayList<ArrayList>();

		for (int i = 0; i <= n; i++) {
			pathList.add(new ArrayList<int[]>());
		}

		for (int i = 0; i < paths.length; i++) {
			int from = paths[i][0];
			int to = paths[i][1];
			int dis = paths[i][2];

			pathList.get(from).add(new int[] { to, dis });
			pathList.get(to).add(new int[] { from, dis });
		}

		Arrays.sort(summits);

		for (int i = 0; i < summits.length; i++) {
			Queue<int[]> queue = new LinkedList<int[]>();
			int[] visited = new int[n + 1];
			Arrays.fill(visited, 10_000_001);
			queue.offer(new int[] { summits[i], 0 });
			visited[summits[i]] = 0;
			int minInten = answer[1];

			while (!queue.isEmpty()) {
				int now = queue.peek()[0];
				int maxInten = queue.poll()[1];

				if (maxInten >= minInten) {
					continue;
				}

				ArrayList<int[]> canMove = pathList.get(now);

				for (int j = 0; j < canMove.size(); j++) {
					int to = canMove.get(j)[0];
					int dis = canMove.get(j)[1];
					int nextInten = Math.max(maxInten, dis);

					if (visited[to] > nextInten) {
						if (gateCheck[to]) {
							visited[to] = nextInten;
							minInten = Math.min(nextInten, minInten);
						} else if (!summitCheck[to]) {
							queue.offer(new int[] { to, nextInten });
							visited[to] = nextInten;
						}
					}
				}
			}

			for (int j = 0; j < gates.length; j++) {
				int goal = gates[j];
				if (visited[goal] < answer[1]) {
					answer[0] = summits[i];
					answer[1] = visited[goal];
				}
			}
		}
		return answer;
	}
}