[PS] BOJ 26125 / 두 도로

Minjun Kim

25 Sep 2025 • 5 min read

Thumbnail: Photo by 50m. above (Unsplash)

문제 링크: https://www.acmicpc.net/problem/26125

플로이드-워셜(Floyd-Warshall) 알고리즘을 활용하는 문제입니다.

풀이

플로이드-워셜(Floyd-Warshall)!

플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로 가는 최단 거리를 탐색하는 방법입니다. 다익스트라 알고리즘이 한 정점에서 다른 모든 정점으로의 최단 거리를 계산하는 점에서 차이가 있습니다.

모든 정점에서 모든 정점으로 가는 최단 거리를 탐색하기 때문에, $O(N^3)$의 시간 복잡도를 가지고 있어 정점의 개수가 적은 문제일 경우에만 사용할 수 있습니다.
또한, 알고리즘에서 각 정점 사이의 최단 거리를 인접 행렬의 형태로 관리하기 때문에, 간선 또한 인접 행렬로 받는 편이 편리합니다.

INF = 1_000_000_001 # 두 정점 사이의 간선이 없는 경우를 나타내는 값

# N: 정점의 개수
# M: 간선의 개수
# S, T: 집과 회사의 위치 (구하려는 최단 경로의 시작 밑 끝점)
N, M, S, T = map(int, input().split())
graph = [[INF for _ in range(301)] for _ in range(301)]   # 방향 그래프
dist = [[INF for _ in range(301)] for _ in range(301)]    # 플로이드-워셜 최단거리 저장용 인접 행렬
for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u][v] = min(graph[u][v], w)

# dist 초기화
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            dist[i][j] = 0
        elif graph[i][j] != INF:
            dist[i][j] = graph[i][j]

# 플로이드-워셜
for mid in range(1, N + 1):
    for i in range(1, N + 1):
        if i == mid:
            continue

        for j in range(1, N + 1):
            if j == mid: 
                continue

            new_dist = dist[i][mid] + dist[mid][j]
            if new_dist < dist[i][j]:
                dist[i][j] = new_dist

인접 행렬로 그래프 입력 받기

INF 값은 적절히 큰 값으로 잡아야 합니다. 두 정점 사이의 거리 (간선의 가중치)가 문제에서는 $10^6$으로 주어졌으나, 그렇다 해서 INF = 1e6 + 1로 쓰게 되면 오답을 받게 됩니다.
(INF끼리 더한 값이 최대 가중치로 이어진 경로(1e6의 합)보다 짧아질 수 있기 때문입니다.)

굳이 원본 그래프 정보를 보존할 필요가 없으므로, 위 코드는 하나의 배열만 쓰도록 간소화할 수 있습니다.

INF = 1_000_000_001

N, M, S, T = map(int, input().split())
graph = [[0 if i == j else INF for i in range(301)] for j in range(301)]   # 방향 그래프

for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u][v] = min(graph[u][v], w)

# 플로이드-워셜
for mid in range(1, N + 1):
    for i in range(1, N + 1):
        if i == mid:
            continue

        for j in range(1, N + 1):
            if j == mid: 
                continue

            new_dist = graph[i][mid] + graph[mid][j]
            if new_dist < graph[i][j]:
                graph[i][j] = new_dist

간소화한 플로이드-워셜

새로 두 개의 다리를 놓기

이제, $Q$개의 시나리오가 주어집니다. 각 시나리오에서는 2개의 다리가 새로 지어지며, 이 다리들을 포함할 때 S -> T의 최단 거리를 구하면 됩니다.

두 개의 다리 $a_1 \rightarrow b_1 (c_1)$, $a_2 \rightarrow b_2 (c_2)$가 새로 지어질 때 경로 $S \rightarrow T$보다 짧아질 수 있는 경로는 4가지 존재합니다.

다리 1만 이용하기
- $S \rightarrow a_1 \rightarrow b_1 \rightarrow T$
- 거리는 dist[$S$][$a_1$] + $c_1$ + dist[$b_1$][$T$]
다리 2만 이용하기
- $S \rightarrow a_2 \rightarrow b_2 \rightarrow T$
- 거리는 dist[$S$][$a_2$] + $c_2$ + dist[$b_2$][$T$]
다리 1 -> 다리 2 순으로 이용하기
- $S \rightarrow a_1 \rightarrow b_1 \rightarrow a_2 \rightarrow b_2 \rightarrow T$
- 거리는 dist[$S$][$a_1$] + $c_1$ + dist[$b_1$][$a_2$] + $c_2$ + dist[$b_2$][$T$]
다리 2 -> 다리 1 순으로 이용하기
- $S \rightarrow a_2 \rightarrow b_2 \rightarrow a_1 \rightarrow b_1 \rightarrow T$
- 거리는 dist[$S$][$a_2$] + $c_2$ + dist[$b_2$][$a_1$] + $c_1$ + dist[$b_1$][$T$]

for i in range(int(input())):
    a1, b1, c1, a2, b2, c2 = map(int, input().split())
    
    # 가능한 4가지 경우 고려하기
    reduced_dist = min(dist[S][T], dist[S][a1] + c1 + dist[b1][T])                          # 1. 도로 1 이용 시 거리
    reduced_dist = min(reduced_dist, dist[S][a2] + c2 + dist[b2][T])                        # 2. 도로 2 이용 시 거리
    reduced_dist = min(reduced_dist, dist[S][a1] + c1 + dist[b1][a2] + c2 + dist[b2][T])    # 3. 도로 1 -> 도로 2 이용 시 거리
    reduced_dist = min(reduced_dist, dist[S][a2] + c2 + dist[b2][a1] + c1 + dist[b1][T])    # 4. 도로 2 -> 도로 1 이용 시 거리
    print(reduced_dist if reduced_dist < INF else -1)

새로 다리를 놓은 뒤의 최단 거리 계산하기

전체 코드

input = open(0).readline
INF = 1_000_000_001

N, M, S, T = map(int, input().split())
graph = [[INF for _ in range(301)] for _ in range(301)]   # 방향 그래프
dist = [[INF for _ in range(301)] for _ in range(301)]    # 플로이드-워셜 최단거리 저장용 인접 행렬
for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u][v] = min(graph[u][v], w)

# dist 초기화
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            dist[i][j] = 0
        elif graph[i][j] != INF:
            dist[i][j] = graph[i][j]

# 플로이드-워셜
for mid in range(1, N + 1):
    for i in range(1, N + 1):
        if i == mid:
            continue

        for j in range(1, N + 1):
            if j == mid: 
                continue

            new_dist = dist[i][mid] + dist[mid][j]
            if new_dist < dist[i][j]:
                dist[i][j] = new_dist

for i in range(int(input())):
    a1, b1, c1, a2, b2, c2 = map(int, input().split())
    
    # 가능한 4가지 경우 고려하기
    reduced_dist = min(dist[S][T], dist[S][a1] + c1 + dist[b1][T])                          # 1. 도로 1 이용 시 거리
    reduced_dist = min(reduced_dist, dist[S][a2] + c2 + dist[b2][T])                        # 2. 도로 2 이용 시 거리
    reduced_dist = min(reduced_dist, dist[S][a1] + c1 + dist[b1][a2] + c2 + dist[b2][T])    # 3. 도로 1 -> 도로 2 이용 시 거리
    reduced_dist = min(reduced_dist, dist[S][a2] + c2 + dist[b2][a1] + c1 + dist[b1][T])    # 4. 도로 2 -> 도로 1 이용 시 거리
    print(reduced_dist if reduced_dist < INF else -1)

solution.py