BOJ 1238 : 파티 [C++]

문제

 

처음에는 dfs로 가능할까? 하고 시도해보려고 했는데,

그냥 문제에서 대놓고 '최단 거리'라고 언급해준 거 최단 거리로 푸는 게 맞겠다 하고 최단 거리로 해결했다.

물론 다익스트라가 기억이 안나서 다른 블로그 참고해서 푼다고 30분이나 걸렸다.

(다익스트라는 유튜브 동빈나 님이 운영하는 블로그를 참고했다.)

 

처음에는 파티 열리는 장소를 시작으로 잡고 다익스트라 한번 돌리면 되겠다라고 생각했는데

예제부터 답이 다르게 나오길래 문제를 다시 읽었다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. 

그리고 왕복 시간 중 가장 많이 소비된 시간을 구하는 문제여서, 거리를 저장하는 배열 dist도 2차원으로 바꾸고,

다익스트라도 모든 마을을 출발점으로 돌렸다.

#include <iostream>
#include <vector>
#include <queue>

static int INF = 200000000;
std::vector<std::pair<int, int>> edges[1001];
int dist[1001][1001];

void dijkstra(int start) {
    dist[start][start] = 0;
    std::priority_queue<std::pair<int, int>> pq;
    pq.push({start, 0});

    while (!pq.empty()) {
        int cur_village = pq.top().first;
        int cur_dist = -pq.top().second;
        pq.pop();

        if (dist[start][cur_village] < cur_dist) {
            continue;
        }

        for (int i = 0; i < edges[cur_village].size(); i++) {
            int next_village = edges[cur_village][i].first;
            int next_dist = cur_dist + edges[cur_village][i].second;

            if (next_dist < dist[start][next_village]) {
                dist[start][next_village] = next_dist;
                pq.push({next_village, -next_dist});
            }
        }
    }
}

int main() {
    int villages = 0, roads = 0, party = 0;
    std::cin >> villages >> roads >> party;

    for (int i = 0; i < roads; i++) {
        int start = 0, dest = 0, t = 0;
        std::cin >> start >> dest >> t;
        edges[start].push_back({dest, t});
    }

    for (int i = 1; i < villages + 1; i++) {
        for (int j = 1; j < villages + 1; j++) {
            dist[i][j] = INF;
        }
    }

    for (int i = 1; i < villages + 1; i++) {
        dijkstra(i);
    }

    int ans = 0;
    for (int i = 1; i < villages + 1; i++) {
        if (dist[i][party] + dist[party][i] > ans) {
            ans = dist[i][party] + dist[party][i];
        }
    }

    std::cout << ans << "\n";

    return 0;
}

 

해결하고서 다른 블로그들 풀이를 보는데,

역방향 간선도 저장해서 다익스트라 두 번만 돌려서 해결하는 풀이가 있다.

역방향 간선을 저장하고 그 간선에 대해 파티를 하는 마을을 기점으로 다익스트라를 돌리면

정방향 간선을 기준으로 각 마을에서 파티를 하는 마을까지의 최단 거리를 얻는 거나 다름이 없다가 핵심인 거 같다.

 

정방향 간선, 역방향 간선에 대해 파티하는 마을을 시작으로 각각 다익스트라 한번

 

정방향 간선을 사용하여 파티하는 마을에서 각 마을까지 최단거리 + 역방향 간선을 사용하여 각 마을에서 파티하는 마을까지 최단거리를 얻을 수 있다.

 

이런 생각은 어떻게 하는거고 대체;;

 

 

 

 

 

 

 

감상

 

일주일동안 문제를 안 풀다가 풀었는데, 골드3 이라 좀 쫄았는데 의외로 금방 풀 수 있었다.

물론 다익스트라 기억이 안나서 구글링 한 건 좀 그렇네;;

그리고 역방향 간선 저장하는 방식은 도대체 어떻게 생각해낸 걸까