문제 링크 ▶︎ 등산코스 정하기
문제 파악
문제에는 산봉우리까지 올라갔다가 다시 내려오면서까지의 intensity의 max가 가장 작은 경로를 탐색하라고 했는데 사실 출발지에서 산봉우리까지만 가면 된다. 어차피 그 경로에서 intensity의 max가 작으면 왕복의 intensity의 max도 작기 때문이다.
그리고 출발지점에 따라 어느 산봉우리에 max intensity가 최소인지를 완전탐색해야 할 것 같다.
또한 intensity가 같을 때는 지점의 number가 작은 값이 우선시되는 것도 인지해야한다.
다익스트라 알고리즘으로 풀면 되지만 여러가지 조건이 많아서 까다로운 문제인 것 같다.
접근 방법
-
target, cost 즉 정답을 이루는 어떤 산봉우리에 얼마의 비용으로 도달했는지를 전역으로 선언하고 max값으로 채워둔다. 그 이유는 최소일때를 계속 갱신해야하기 때문이다.
-
해시맵은 만들고 양방향으로 노드와 비용을 기록해둔다.
-
cal 이라는 함수를 만들어서 특정 출발지점에서 어떤 산봉우리에 max intensity가 적은지를 체크하는 로직을 만드는데 이때, 매개 변수로는 n, 시작점 배열인 gates, 산봉우리 배열인 summits, map으로 받는다.
-
우선순위 큐는 큐안의 int배열의 1번째 인덱스, 0번째 인덱스 순으로 정렬한다. 그 이유는 만약에 intensity가 같으면 넘버가 작은 산봉우리가 우선 순위를 갖기 때문이다.
-
pq에 시작점과 0 을 넣고, 모든 정수배열 visit은 최댓값으로 채워두고 모든 시작점만 0으로 바꿔놓는다.
모든 시작점을 0으로 바꾸는 이유는 다른 시작점으로 도달하면 안되기 때문이다. -
while문을 돌면서 다익스트라 알고리즘을 구현하고, 만약 최소비용이 갱신됐거나, 아니면 최소비용은 갱신되지않고 같은데 산봉우리 넘버가 더 작은 경우에는 답을 갱신한다.
-
다시 solution으로 돌아와서 모든 시작점에서 cal 함수를 호출하고 갱신된 답을 리턴한다.
코드 구현
import java.util.*;
class Solution {
public int target;
public int cost;
public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
target = Integer.MAX_VALUE;
cost = Integer.MAX_VALUE;
Map<Integer,List<int[]>> map = new HashMap<>();
for(int i=1; i<=n; i++){
map.put(i,new ArrayList<>());
}
for(int[] path : paths){
int a = path[0], b = path[1], dist = path[2];
map.get(a).add(new int[] {b,dist});
map.get(b).add(new int[] {a,dist});
}
for(int gate : gates){
cal(n,gates,gate, map, summits);
}
int[] answer = new int[]{target, cost};
return answer;
}
public void cal(int n, int[] gates, int start, Map<Integer,List<int[]>> map, int[] summits){
Queue<int[]> pq = new PriorityQueue<>((a,b) -> {
if (a[1] != b[1]) {
return a[1] - b[1];
} else {
return a[0] - b[0];
}
});
pq.add(new int[]{start,0});
int[] visit = new int[n+1];
Arrays.fill(visit,Integer.MAX_VALUE);
for(int gate : gates){
visit[gate] = 0;
}
out:
while(!pq.isEmpty()){
int[] out = pq.remove();
int now = out[0], now_dist = out[1];
for(int summit : summits){
if(now == summit){
if(cost > now_dist || (cost == now_dist && target > summit)){
target = summit;
cost = now_dist;
}
break out;
}
}
for(int[] arr : map.get(now)){
int next = arr[0], next_dist = arr[1];
int real_dist = Math.max(next_dist,now_dist);
if(visit[next] > real_dist){
visit[next] = real_dist;
pq.add(new int[] {next, real_dist});
}
}
}
}
}개선 사항
if(cost > now_dist || (cost == now_dist && target > summit))
이 부분에서 intensity는 같은데 산봉우리 넘버 비교를 안해서 시간을 허비했다.
원래보다 더 까다로운 문제인 것 같아서 좋은 경험을 했다!
