[프로그래머스/자바] 등산코스 정하기 풀이 - 2020 KAKAO TECH INTERNSHIP

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

프로그래머스

 

2020 KAKAO TECH INTERNSHIP의 Level 3 문제다.

 

 

산봉우리에 도착후 다시 똑같은 코스로 출입구에 돌아와야 intensity가 최소가 되므로

하나의 출입구를 시작으로 산봉우리에 도착할 때만 고려해도 된다.

 

처음엔 BFS로 풀다가

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

위 링크를 참고해서 풀었다.

 

intensity[] 배열을 만들어 이 배열의 인덱스로 갈 수 있는 최소 intensity를 갱신하며

다익스트라 알고리즘을 진행하면 된다.

일반 다익스트라 알고리즘처럼 모든 경로의 비용 합을 고려하는 것이 아닌

두 지점 간 비용(휴식시간)만 비교하는 다익스트라 라는 것이 핵심이다.

 

막상 다 풀었을 땐 생각보다 간단하게 느껴졌는데, 접근방식을 생각하기가 어려웠다.

그래프 문제가 나오면 가장 익숙한 BFS/DFS를 사용하는 것 같다.

다익스트라나 플로이드워셜 등 다양한 그래프 알고리즘을 연습해봐야겠다는 생각..

 

 

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

class Solution {
	static int[] intensity;
	static boolean[] isSummit;
	static boolean[] isGate;
	static ArrayList<int[]> list[];
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
		list = new ArrayList[n + 1];
		intensity = new int[n + 1];
		isSummit = new boolean[n + 1];
		isGate = new boolean[n + 1];
		
		for(int i=0;i<gates.length;i++)
			isGate[gates[i]] = true;

		for(int i=0;i<summits.length;i++)
			isSummit[summits[i]] = true;

		for(int i=1;i<=n;i++)
			list[i] = new ArrayList<>();

		for(int i=0;i<paths.length;i++) {
			int edge1 = paths[i][0];
			int edge2 = paths[i][1];
			int weight = paths[i][2];

			// 산봉우리, 출입구 단방향
			if(isSummit[edge2] || isGate[edge1])
				list[edge1].add(new int[] {edge2, weight});
			else if(isSummit[edge1] || isGate[edge2])
				list[edge2].add(new int[] {edge1, weight});
			else {
				list[edge1].add(new int[] {edge2, weight});
				list[edge2].add(new int[] {edge1, weight});
			}
		}

		dijkstra(n, gates, summits);

		Arrays.sort(summits); // intensity가 같은 경우 산봉우리가 작은 걸 선택해야 하므로
		int mount = -1;
		int inten = Integer.MAX_VALUE;
		
		for(int i : summits) {
			if(intensity[i] < inten) {
				mount = i;
				inten = intensity[i];
			}
		}

		return new int[] {mount, inten};
	}

	static void dijkstra(int n, int[] gates, int[] summits) {
		Queue<int[]> q = new LinkedList<>(); // 정점, 거리
		Arrays.fill(intensity, Integer.MAX_VALUE);

		// 출입구 큐에 넣기
		for(int g : gates) {
			q.offer(new int[] {g, 0});
			intensity[g] = 0;
		}

		while(!q.isEmpty()) {
			int[] arr = q.poll();
			int edge = arr[0];
			int weight = arr[1];

			// 최소 갱신 안되는 경우 스킵
			if(weight > intensity[edge])
				continue;

			for(int[] next : list[edge]) {
				int nextEdge = next[0];
				int nextWeight = next[1];
				
				int temp = Math.max(intensity[edge], nextWeight);
				if(intensity[nextEdge] > temp) {
					intensity[nextEdge] = temp;
					q.add(new int[] {nextEdge, temp});
				}
			}
		}
	}
}