[프로그래머스] 등산코스 정하기

문제 설명

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

문제 풀이

• 문제를 풀기 위해 사용했던 인사이트는 다음과 같다.

  • 왕복을 구할 필요 없이 정상까지 편도 최소값을 구하면 된다.
    (시작점 -> 정상 최소값 <= 정상 -> 시작점 코스트)
  • 다익스트라 알고리즘을 모든 출발지점에 대해 돌리지 않고 한번의 다익스트라 알고리즘을 돌리되 모든 출발 지점을 초기에 넣어준다.
  • 다익스트라 알고리즘 진행 중 정상에 닿으면 진행을 멈춘다.

• 우선 1번은 명확하다 시작점부터 특정 정상까지 여러 코스가 있을때 시작점 -> 정상 경로의 최소 코스트는 정상 -> 시작점으로 되돌아 오는 모든 코스의 코스트보다 작거나 같다.
  따라서 해당 문제는 다익스트라 알고리즘을 이용한 최단 거리 문제로 좁힐 수 있다.
• 2번의 경우 만약 모든 지점에 대해 다익스트라 알고리즘을 돌린다면 O(N logV) N = 약 500억 정도의 코스트이므로 시간 초과가 발생한다.
• 모든 지점을 초기에 넣어줄 경우 각 출발점의 dist값은 0이 되기 때문에 자연스럽게 출발지점이 중복될 문제는 없어지고 모든 출발점에 대해 가장 가까운 정상을 구할 수 있다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int INF = 987654321;
    public class Point implements Comparable<Point> {
        int n, c;

        public Point (int n, int c) {
            this.n = n;
            this.c = c;
        }

        @Override
        public int compareTo(Point t) {
            return this.c - t.c;
        }
    }

    public List<List<Point>> map = new ArrayList<>();

    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        boolean[] isTop = new boolean[n+1];
        //초기화
        Arrays.sort(summits);
        for (int i = 0; i <= n; i++)
            map.add(new ArrayList<>());
        for (int i = 0; i < paths.length; i++) {
            int from = paths[i][0];
            int to = paths[i][1];
            int c = paths[i][2];
            map.get(from).add(new Point(to, c));
            map.get(to).add(new Point(from, c));
        }
        for (int i = 0; i < summits.length; i++)
            isTop[summits[i]] = true;

        //다익스트라 알고리즘
        int[] dist = new int[n+1];
        Arrays.fill(dist, INF);
        PriorityQueue<Point> pq = new PriorityQueue<>();
        for (int i = 0; i < gates.length; i++) {
            dist[gates[i]] = 0;
            pq.add(new Point(gates[i], 0));
        }
        while(!pq.isEmpty()) {
            Point cur = pq.poll();
            if (isTop[cur.n]) continue;
            if (dist[cur.n] < cur.c) continue;
            for (int i = 0; i < map.get(cur.n).size(); i++) {
                int nextN = map.get(cur.n).get(i).n;
                int nextC = Math.max(map.get(cur.n).get(i).c, cur.c);
                if (dist[nextN] > nextC) {
                    dist[nextN] = nextC;
                    pq.add(new Point(nextN, nextC));
                }
            }
        }

        //결과 출력
        int resC = INF;
        int resT = 0;
        for (int i = 0; i < summits.length; i++) {
            if (dist[summits[i]] < resC) {
                resC = dist[summits[i]];
                resT = summits[i];
            }
        }
        return new int[]{resT, resC};
    }
}