[Programmers] 118669번 - 등산코스 정하기 [Java][C++]

문제 링크

---

1. 아이디어

주어진 등산로에 대해 출입구에서 다른 출입구를 거치지 않으면서 산봉우리를 발견한 후 다시 출발한 곳으로 돌아오는 경우 최소 intensity를 구하는 문제로 왔던 길을 다시 갈 수 있으므로 각 출입구에서 최소 intensity로 산봉우리를 갈 수 있는 모든 경로를 찾아서 그중에서 최소 intensity이면서, intensity가 같으면 산봉우리 번호가 작은 경로를 찾아야 한다.

해당 문제는 다익스트라 알고리즘을 활용하면 해결할 수 있는데 주어진 모든 출입구를 먼저 우선순위 큐에 넣어주는 멀티 서치를 활용했다. 우선순위 큐의 경우 번호와 현재 경로의 intensity를 받는 객체를 활용했고 intensity에 대한 오름차순으로 정렬하여 최소 intensity를 우선으로 탐색하도록 해줬다. 다음 경로가 출입구거나 이미 방문한 곳이면 넘어갔고 산봉우리를 발견하면 intensity가 최소인 경로인지, 동일하다면 산봉우리 번호가 최소인지 비교해나가는 과정을 반복해줬다.

다익스트라 알고리즘의 코드 베이스를 활용하지만 경로 누적이 아닌 최댓값만 취해야 함에 주의해야 한다.

---

2. 복잡도

시간복잡도	공간복잡도
$O((V + E) \log V)$	$O(V + E)$

$V$ = 지점 수 n, $E$ = paths 개수

---

3. 코드

풀이 [Java][C++]

import java.util.*;

class Solution {

    static int INF = 10_000_001;

    static class Node implements Comparable<Node> {
        int v;
        int w;

        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.w, o.w);
        }
    }

    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        List<Node>[] adj = new ArrayList[1 + n];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] path : paths) {
            adj[path[0]].add(new Node(path[1], path[2]));
            adj[path[1]].add(new Node(path[0], path[2]));
        }

        boolean[] isGate = new boolean[1 + n];
        boolean[] isSummit = new boolean[1 + n];
        for (int gate : gates) {
            isGate[gate] = true;
        }
        for (int summit : summits) {
            isSummit[summit] = true;
        }

        return dijkstra(gates, n, adj, isGate, isSummit);
    }

    static int[] dijkstra(int[] gates, int n, List<Node>[] adj, boolean[] isGate, boolean[] isSummit) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int gate : gates) {
            pq.offer(new Node(gate, 0));
        }

        boolean[] vis = new boolean[1 + n];

        int[] ans = new int[]{0, INF};

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (isSummit[cur.v]) {
                if (cur.w < ans[1] || cur.w == ans[1] && cur.v < ans[0]) {
                    ans[0] = cur.v;
                    ans[1] = cur.w;
                }
                continue;
            }

            if (vis[cur.v]) continue;
            vis[cur.v] = true;

            for (Node nxt : adj[cur.v]) {
                if (isGate[nxt.v] || vis[nxt.v]) continue;
                pq.offer(new Node(nxt.v, Math.max(cur.w, nxt.w)));
            }
        }

        return ans;
    }
}

pair의 정렬 기준을 그대로 활용하기 위해 first에 intensity를, second에 번호를 저장해줬다.

#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int INF = 10'000'001;
const int MAXN = 50'000;

bool isGate[1 + MAXN];
bool isSummit[1 + MAXN];

vector<pair<int, int>> adj[1 + MAXN];
bool vis[1 + MAXN];

vector<int> dijkstra(vector<int>& gates) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (int gate : gates) {
        pq.push({0, gate});
    }

    vector<int> ans = {0, INF};

    while (!pq.empty()) {
        auto [cur_w, cur_v] = pq.top();
        pq.pop();

        if (isSummit[cur_v]) {
            if (cur_w < ans[1] || cur_w == ans[1] && cur_v < ans[0]) {
                ans[0] = cur_v;
                ans[1] = cur_w;
            }
            continue;
        }

        if (vis[cur_v]) continue;
        vis[cur_v] = true;

        for (auto [nxt_w, nxt_v] : adj[cur_v]) {
            if (isGate[nxt_v] || vis[nxt_v]) continue;
            pq.push({max(cur_w, nxt_w), nxt_v});
        }
    }

    return ans;
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for (auto& path : paths) {
        adj[path[0]].push_back({path[2], path[1]});
        adj[path[1]].push_back({path[2], path[0]});
    }

    for (int gate : gates) {
        isGate[gate] = true;
    }
    for (int summit : summits) {
        isSummit[summit] = true;
    }

    return dijkstra(gates);
}

---

4. 리뷰

n = 4, paths = [[1, 3, 10], [1, 4, 10], [4, 2, 5]], gates = [1], summits = [2, 3]인 입력에서 Return이 [2, 10]이 나와야 하는데 [3, 10]이 나오는 코드가 AC가 됐었다. 동일한 intensity에서 산봉우리 번호가 가장 작은 게 잘 나오는지 꼼꼼한 확인이 필요한 것 같다.

---