문제 개요
n개의 도시와 이들을 연결하는 m개의 도로가 있다고 가정해 봅시다. 모든 도로는 일방통행이며, 출발 도시에서 목적지 도시까지 이동하는 데 일정한 시간이 걸립니다. 도로 정보는 roads 배열에 담겨 있으며, 각 원소는 (출발지, 목적지, 소요 시간) 형식을 따릅니다.
어떤 사람이 한 도시에서 출발해 다시 같은 도시로 돌아오는 왕복 여행(round-trip)을 하려고 합니다. 왕복 여행이란 특정 도시에서 시작해 하나 이상의 도로를 지나 다시 출발했던 도시에서 끝나는 경로를 의미합니다. 따라서 우리는 각 도시마다 그 도시에서 왕복 여행이 가능한지 판별해야 하며, 가능하다면 왕복에 필요한 시간을, 불가능하다면 -1을 출력해야 합니다.
예를 들어 입력이 n = 4, m = 4, roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}이라면 출력은 26 26 26 26이 됩니다. 네 도시가 하나의 순환 구조를 이루고 있으므로, 어느 도시에서 출발하더라도 전체 도로를 한 바퀴 돌아 왕복하는 데 걸리는 시간은 26으로 동일합니다.
해결 접근 방법
이 문제는 각 도시를 시작점으로 삼아 우선순위 큐(priority queue)를 활용한 다익스트라(Dijkstra) 스타일의 탐색을 수행함으로써 해결할 수 있습니다. 탐색 과정에서 출발 도시로 다시 돌아오는 순간의 누적 시간이 곧 해당 도시의 왕복 소요 시간이 됩니다.
알고리즘 단계
다음 순서대로 진행합니다 −
pair의 2차원 배열 graph(n)을 정의한다
i := 0으로 초기화하고, i < m인 동안 i를 1씩 증가시키며 반복:
x := roads[i]의 첫 번째 값
y := roads[i]의 두 번째 값
z := roads[i]의 세 번째 값
x와 y를 각각 1만큼 감소시킨다
graph[x]의 끝에 pair (y, z)를 삽입한다
i := 0으로 초기화하고, i < n인 동안 i를 1씩 증가시키며 반복:
q := 새로운 우선순위 큐
배열 dst를 정의한다
q의 맨 앞에 pair (0, i)를 삽입한다
q의 크기가 0이 아닌 동안 반복:
pair p := q의 top 값
q에서 top 원소를 제거한다
dt := p의 첫 번째 값
curr := p의 두 번째 값
만약 dst[curr] == 0이라면:
dst[curr] := dt
루프를 빠져나간다
만약 dst[curr] != -1이라면:
아래 부분을 무시하고 다음 반복으로 건너뛴다
dst[curr] := dt
graph[curr]의 각 원소 next에 대해:
tp := next의 첫 번째 값
cst := next의 두 번째 값
q에 pair (dt + cst, tp)를 삽입한다
만약 dst[i] == 0이라면:
dst[i] := -1
dst[i]를 출력한다
예제 구현
아래 구현 예시를 통해 더 잘 이해해 봅시다 −
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int modval = (int) 1e9 + 7;
#define N 100
void solve(int n, int m, vector<tuple<int, int, int>> roads ) {
vector<vector<pair<int, int>>> graph(n);
for(int i = 0; i < m; i++) {
int x, y, z;
tie(x, y, z) = roads[i];
x--; y--;
graph[x].emplace_back(y, z);
}
for(int i = 0; i < n; i++) {
priority_queue<pair<int, int>> q;
vector<int> dst(n, -1);
q.emplace(0, i);
while(q.size()){
pair<int, int> p = q.top();
q.pop();
int curr, dt;
tie(dt, curr) = p;
if(dst[curr] == 0) {
dst[curr] = dt;
break;
}
if(dst[curr] != -1)
continue;
dst[curr] = dt;
for(auto next : graph[curr]){
int tp, cst;
tie(tp, cst) = next;
q.emplace(dt + cst, tp);
}
}
if(dst[i] == 0)
dst[i] = -1;
cout<< dst[i]<< endl;
}
}
int main() {
int n = 4, m = 4;
vector<tuple<int, int, int>> roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}};
solve(n, m, roads);
return 0;
}
입력
4, 4, {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}
출력
26 26 26 26
동작 설명
코드는 먼저 도로 정보를 인접 리스트 형태의 그래프로 변환합니다. 이때 도시 번호는 0부터 시작하도록 1씩 줄여 저장합니다. 이후 각 도시를 시작점으로 삼아 우선순위 큐에 (누적 시간, 도시) 쌍을 넣고 탐색을 진행합니다. 이미 방문한 도시는 건너뛰며, 탐색 도중 출발 도시(dst 값이 0인 상태)에 다시 도달하면 그 순간의 누적 시간을 왕복 시간으로 기록하고 종료합니다. 만약 큐가 비워질 때까지 출발 도시로 돌아오지 못했다면 왕복이 불가능한 것이므로 -1을 출력합니다.