[백준 1504번] 특정한 최단 경로(C++)

Baekjoon Online Judge 에 올라온 문제에 대해 정리하고자 글을 쓰고 있습니다. 많은 피드백 부탁드립니다!

BOJ 1504 바로가기

https://www.acmicpc.net/problem/1504

요구사항

undirected graph
1 ~ N 까지의 최단 거리
간선의 weight은 0 이상
단, 주어지는 두 정점을 반드시 통과해야 한다.
한 번 이동했던 정점을 지날 수 있다.
한 번 이동했던 간선도 지날 수 있다.

위 조건을 만족하면서, 1번 정점부터 N번 정점까지의 최단거리를 구해보자.

Idea

먼저 간선의 weight이 0 이상임을 보고 Dijkstra 알고리즘을 사용할 수 있다는 것을 눈치 챘을 것이다. 그렇다면, 특정 두 정점을 지나는 최단거리는 어떻게 구할 수 있을까?

Dijkstra 로직을 세 번 써보자!

아이디어는 이러하다. 지나야 하는 정점 2개를 각각 v1과 v2라고 할 때, 총 두가지 경우가 나온다.

(1번 정점에서 v1까지의 최단거리) + (v1에서 v2까지의 최단거리) + (v2에서 N번 정점까지의 최단거리)
(1번 정점에서 v2까지의 최단거리) + (v2에서 v1까지의 최단거리) + (v1에서 N번 정점까지의 최단거리)

이 두가지 경우 중 결과값이 작은 경우가 정답이 된다.

예외처리

예외처리를 생각해보자.

v1 : v1 = 1이 될 수 있다.
v2 : v2 = 2가 될 수 있다.

즉 자기 자신으로 향하는 self edge를 생각해봐야 한다. 이에 따라 자기 자신으로의 weight는 0으로 해두는 것이 좋다. 보통 한 정점을 기준으로 하는 각 노드들의 최단거리들을 dist 배열에 저장하는데, 이 때, 자기 자신에 해당하는 index에는 0으로 초기화를 해주는 것을 잊지 말아야 한다.

로직

1번 노드를 시작점으로 하는 Dijkstra 알고리즘을 수행하여 dist 배열을 얻는다.
마찬가지로 v1과 v2 노드를 시작점으로 하는 Dijkstra 알고리즘을 수행하여 각각의 dist 배열을 얻는다.
위에서 언급했던 나올 수 있는 두가지 경우에 대해서 dist 배열로부터 값을 얻어 계산한다. 이 경우 distance가 INF인 경우를 생각해야 한다.
두가지 경우 중 작은 것을 정답으로 출력한다. 이 때, 두가지 경우 모두 distance로 INF를 가지는 경우 -1을 출력한다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAX 800
#define INFTY 0x3f3f3f3f

typedef long long ll;

int Dist[3][MAX + 1];
int N, M, V1, V2;
long long Answer;
vector<pair<int, int> > Graph[MAX + 1];

void input(void)
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        Graph[a].push_back(make_pair(c, b));
        Graph[b].push_back(make_pair(c, a));
    }
    cin >> V1 >> V2;
}

void dijkstra(int s, int type)
{
    priority_queue<pair<int,int> > pq;
    pq.push(make_pair(0, s));

    while (!pq.empty())
    {
        int u = pq.top().second;
        int cost = pq.top().first; pq.pop();

        vector<pair<int, int> > &adjs = Graph[u];
        int size = adjs.size();

        for (int i = 0; i < size; i++)
        {
            int v = adjs[i].second;
            int weight = adjs[i].first;
            if (cost + weight < Dist[type][v])
            {
                Dist[type][v] = cost + weight;
                pq.push(make_pair(cost + weight, v));
            }
        }
    }
}

void solve(void)
{
    memset(Dist[0], INFTY, sizeof(int) * (MAX + 1));
    Dist[0][1] = 0;
    dijkstra(1, 0);
    memset(Dist[1], INFTY, sizeof(int) * (MAX + 1));
    Dist[1][V1] = 0;
    dijkstra(V1, 1);
    memset(Dist[2], INFTY, sizeof(int) * (MAX + 1));
    Dist[2][V2] = 0;
    dijkstra(V2, 2);

    bool flag1 = Dist[0][V1] == INFTY || Dist[1][V2] == INFTY || Dist[2][N] == INFTY
    bool flag2 = Dist[0][V2] == INFTY || Dist[2][V1] == INFTY || Dist[1][N] == INFTY
    ll result1 = (ll)Dist[0][V1] + Dist[1][V2] + Dist[2][N];
    ll result2 = (ll)Dist[0][V2] + Dist[2][V1] + Dist[1][N]

    if (flag1)
    {
        if (flag2)
            Answer = -1;
        else
            Answer = result2;
    }
    else
    {
        if (flag2)
            Answer = result1;
        else
            Answer = min(result1, result2);
    }
}

void output(void)
{
    cout << Answer << "\n";
}

int main(void)
{
    cin.tie(NULL)->sync_with_stdio(false);

    input();
    solve();
    output();
}

저작자표시

jungcow