BOJ 14548 - The fastest road to banikoara 링크
(2023.04.19 기준 G4)

문제

두 마을을 잇는 N개의 도로가 주어질 때, A 마을과 B 마을의 최단 경로의 거리 출력

알고리즘

두 마을 간 최단 경로이므로 다익스트라. 그리고 정점 번호가 아닌 마을 이름으로 주어지므로 해시 맵을 이용하자.

풀이

이 문제에선 정점 번호가 아닌 마을 이름으로 모든 정점이 주어진다.
이는 해시 맵을 이용하자.

마을 이름이 주어질 때마다, 해시 맵에 들어가 있는 마을 이름인지 확인하자. 만약 들어가 있지 않다면? 지금까지의 해시 맵 안에 들어가 있는 마을의 개수를 값으로 하여 해시 맵에 저장하면 된다. (0-based index)

잘 생각해보자. 아무것도 들어 있지 않은 해시 맵이 있다. 그러면 처음 마을 이름이 주어진다면? 당연히 처음 번호는 0번이 되어야 하고 이는 해시 맵 안 키의 개수와 같다.

이제 해시 맵으로 마을 이름마다 각 번호가 정해졌다. 이제 남은 것은? 간단한 다익스트라 뿐.

코드

• C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int inf = 1e9;

vector<vector<pii>> graph;
map<string, int> towns;

int idx(string town){ // 마을의 키(정점 번호) 구하기
    if (towns.find(town) == towns.end()){ // 처음 나온 마을이면
        towns.insert({town, towns.size()}); // 키 번호를 새로 할당
        graph.emplace_back(); // 그래프의 크기도 늘려야 한다.
    }
    return towns[town];
}

void solve(){
    int n = 0;
    graph.clear();
    towns.clear();

    // 최단 경로를 구해야 하는 두 마을의 이름은 나중에 출력해야 하므로 따로 저장해두자.
    int N; string st, en;
    cin >> N >> st >> en;
    int s = idx(st), e = idx(en);

    string town_1, town_2; int a, b, d;
    while (N--){
        cin >> town_1 >> town_2 >> d;
        a = idx(town_1), b = idx(town_2); // 이름을 번호로 바꾸자.

        // 간선 추가
        graph[a].push_back({b, d});
        graph[b].push_back({a, d});
    }

    // 다익스트라
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, s});
    int distance[towns.size()];
    fill(distance, distance + towns.size(), inf);
    distance[0] = 0;
    while (!pq.empty()){
        pii here = pq.top(); pq.pop();
        if (distance[here.second] < here.first) continue;
        for (pii there: graph[here.second]) if (distance[there.first] > here.first + there.second){
            distance[there.first] = here.first + there.second;
            pq.push({distance[there.first], there.first});
        }
    }

    cout << st << ' ' << en << ' ' << distance[e] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int P;
    cin >> P;
    while (P--) solve();
} 

• Python

import sys; input = sys.stdin.readline
from math import inf
from heapq import heappop, heappush

def idx(town): # 마을의 키(정점 번호) 구하기
    if town not in towns: # 처음 나온 마을이면
        towns[town] = len(towns) # 키 번호를 새로 할당
        graph.append([]) # 그래프의 크기도 늘려야 한다.
    return towns[town]

for _ in range(int(input())):
    n = 0
    graph = []
    towns = dict()

    N, start, end = input().split()
    s = idx(start) # 최단 경로를 구해야 하는 두 마을의 이름은 나중에 출력해야 하므로
    e = idx(end) # 따로 저장해두자.

    for _ in range(int(N)):
        a, b, d = input().split()
        a = idx(a) # 이름을 번호로 바꾸자.
        b = idx(b)

        # 간선 추가
        d = int(d) 
        graph[a].append((b, d))
        graph[b].append((a, d))

    # 다익스트라
    queue = [(0, s)]
    distance = [inf] * len(towns)
    distance[s] = 0
    while queue:
        d, here = heappop(queue)
        if distance[here] < d:
            continue
        for there, dd in graph[here]:
            if distance[there] > d + dd:
                distance[there] = d + dd
                heappush(queue, (distance[there], there))

    print(start, end, distance[e])