[프로그래머스] 118669 등산코스 정하기 (C/C++)

문제

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

풀이

문제를 읽고 그래프 탐색으로 해결해야 한다고 판단했고, 가장 먼저 다익스트라 알고리즘을 떠올렸다. 처음에는 각 출발지마다 각 도착지까지의 결과 값이 다를 것이라 생각하여, distance 테이블을 2차원 배열로 구현하였다. 즉, 출발지마다 다익스트라 알고리즘을 수행하고, 각 출발지에서 각 도착지까지의 최소 거리를 구한 뒤 최종 결과를 도출하는 방식으로 접근했다.

하지만 이 방식은 시간 초과가 발생했다. 이에 알고리즘을 다시 고민한 결과, 최종적으로 문제에서 요구하는 것은 도착지까지의 최소 거리였기 때문에, 출발지 별 계산이 아니라 도착지를 기준으로 한 1차원 배열 탐색 방식으로 단순화할 수 있었다. 시간 복잡도를 기존 O(G * (E + V) log V)에서 O((E + V) log V) 즉, O(N^2 * logN)에서 O(N * logN)으로 개선할 수 있었다.

마지막에 답을 도출하는 과정에서 summits배열이 정렬이 되어있다고 가정하고 풀었는데 틀렸다. 정렬 되어있지 않은가보다 하고 std::min_element를 사용해서 답을 도출하도록 수정하여 통과했다.

소스 코드

C++17

#include <bits/stdc++.h>

std::vector<std::vector<std::pair<int, int>>> build_graph(const int n, std::vector<std::vector<int>> &paths) {
    std::vector<std::vector<std::pair<int, int>>> ret(n + 1);

    for (const auto &path: paths) {
        ret[path[0]].push_back({ path[1], path[2] });
        ret[path[1]].push_back({ path[0], path[2] });
    }

    return ret;
}

std::vector<int> mark_summits(const int n, const std::vector<int> &summits) {
    std::vector<int> ret(n + 1, false);

    for (const int summit: summits) {
        ret[summit] = true;
    }

    return ret;
}

std::vector<int> solution(int n, std::vector<std::vector<int>> paths, std::vector<int> gates, std::vector<int> summits) {
    const auto &graph = build_graph(n, paths);
    const auto &is_summit = mark_summits(n, summits);
    std::vector<int> distance(n + 1, INT_MAX);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

    for (const int gate: gates) {
        distance[gate] = 0;
        pq.push({ 0, gate });
    }

    while (!pq.empty()) {
        const auto [ current_distance, current ] = pq.top(); pq.pop();

        if (distance[current] < current_distance || is_summit[current]) {
            continue;
        }

        for (const auto [ next, next_dist ]: graph[current]) {
            if (std::max(current_distance, next_dist) < distance[next]) {
                distance[next] = std::max(current_distance, next_dist);
                pq.push({ distance[next], next });
            }
        }
    }

    auto iter = std::min_element(
        summits.cbegin(), summits.cend(),
        [&] (int lhs, int rhs) {
            if (distance[lhs] == distance[rhs]) {
                return lhs < rhs;
            }
            return distance[lhs] < distance[rhs];
        }
    );

    return { *iter, distance[*iter] };
}

[프로그래머스] 118669 등산코스 정하기 (C/C++)

문제

풀이

소스 코드

Share this post