Java - [프로그래머스]118669 - Lv3.등산코스 정하기

출처

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

프로그래머스

 

문제

한 출입구에서 출발하여 하나의 정상만을 거쳐 되돌아 오려고 한다. 이때, Intensity란 방문한 경로들 중 최대 가중치 값을 의미한다. 이 Intensity가 최소가 되도록 하는 경로를 구하여, 최소 intensity를 가지는 경로의 방문한 산봉우리 값과 , 최소 intensity값을 반환하는 문제이다.

 

풀이

문제에서는, 한 출입구로 부터 출발하여 한 산봉우리까지 갔다가 돌아올 때, Intensity가 최소인 경로를 찾는 문제이다. 이때, 꼭 되돌아 오지 않아도 된다. 최소의 Intensity로 올라갔다면, 돌아올때의 경로도 올라갔던 경로를 따라 내려오는게 최소가 되기 때문에 동일할 수 밖에 없다.

 

따라서, 한 출입구로 부터 한 정상 까지 올라가는 경로 중 Intensity가 최소가 되는 값을 고르면 된다.

 

기존의 다익스트라 알고리즘은, 시작 노드부터 모든 노드 까지의 최단 경로(최소 비용 경로)를 구하는 알고리즘이다. 최소 비용 경로를 계산하는 방법은 경로가 가지는 edge 가중치의 총 합을 기준으로 계산하였다.

 

이 문제에서는, 현재까지의 가중치의 총 합 대신 현재 가중치들 중 최대값 (Intensity)를 기준으로 계산하면 해결할 수 있다. 따라서, 기존 다익스트라 알고리즘에서 Intensity를 최소가 되게끔 수정하면 해결할 수 있다.

 

코드

주어지는 그래프를 자신이 다루기 편한 방식으로 정의해놓으면 문제를 해결하기가 수월하다.

 

 간선의 정보를 담을 Map 자료구조를 만들어서 무방향 그래프를 만들어 내었다. 이때, Edge 클래스를 정의하여 향후 PriorityQueue에서 우선순위를 가려낼 수 있도록 하였다. (Comparable 구현)

 

이후, 위에서 설명한 대로 조건을 바꾸어 다익스트라 알고리즘을 수행하면 원하는 정답을 찾을 수 있다.

import java.util.*;

class Solution {
    
    class Edge implements Comparable<Edge> {
        int node;
        int intense;
        
        public Edge(int node, int intense) {
            this.node = node;
            this.intense = intense;
        }
        
        @Override
        public int compareTo(Edge diff) {
            return this.intense - diff.intense;
        }
    }
    
    Map<Integer, List<Edge>> map = new HashMap<>();
    Set<Integer> set = new HashSet<>();
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = new int[2];
        answer[1] = Integer.MAX_VALUE;
        for (int x : summits) {
            set.add(x);
        }
        
        for (int i = 1; i <= n; i++) {
            map.put(i, new ArrayList<>());
        }
        for (int[] path : paths) {
            map.get(path[0]).add(new Edge(path[1], path[2]));
            map.get(path[1]).add(new Edge(path[0], path[2]));
        }
        
        int[] visited = new int[n+1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        Queue<Edge> pq = new PriorityQueue<>();
        for (int x : gates) {
            pq.add(new Edge(x, 0));
            visited[x] = 0;
        }
        
        while (!pq.isEmpty()) {
            Edge now = pq.poll();
            if (visited[now.node] < now.intense || set.contains(now.node)) continue;
            
            for (Edge next : map.get(now.node)) {
                int nextIntense = Math.max(next.intense, now.intense);
                if (visited[next.node] > nextIntense){
                    visited[next.node] = nextIntense;
                    pq.add(new Edge(next.node, visited[next.node]));
                }
            }
        }
        for (int x: summits) {
            if (visited[x] == answer[1]) {
                if (answer[0] > x) {
                    answer[0] = x;
                }
            }
            else if (visited[x] < answer[1]) {
                answer[0] = x;
                answer[1] = visited[x];
            }
        }
        return answer;
    }
}