🚀 문제
https://www.acmicpc.net/problem/12956
🚀 정답 코드
1️⃣ 플로이드-워셜 버전 ( 시간 초과 발생 )
import copy
import sys
input = sys.stdin.readline
# 도시 수 N, 도로 수 M 입력
N, M = map(int, input().split())
# 인접 행렬 초기화 (무한대), 자기 자신은 거리 0
graph = []
for i in range(N):
row = [float('inf')] * N
row[i] = 0
graph.append(row)
# 도로 정보 입력 및 그래프 구성
cost_input = []
for _ in range(M):
f, t, time = map(int, input().split())
cost_input.append([f, t, time])
graph[f][t] = time
graph[t][f] = time # 무방향 그래프
# 플로이드 워셜 알고리즘으로 최단 거리 계산
def minimum_cost_graph(graph):
new_graph = copy.deepcopy(graph)
for k in range(N):
for i in range(N):
for j in range(N):
if new_graph[i][j] > new_graph[i][k] + new_graph[k][j]:
new_graph[i][j] = new_graph[i][k] + new_graph[k][j]
return new_graph
# 원래 그래프에서 모든 정점쌍의 최단 거리 계산
origin_cost = minimum_cost_graph(graph)
# 결과를 저장할 리스트 (각 간선마다 영향을 받는 최단 경로 수)
result = [0] * M
# 각 간선 하나씩 제거해보며 최단 경로에 영향을 주는지 확인
for idx, (f, t, time) in enumerate(cost_input):
# 간선 (f, t) 제거
graph[f][t] = float('inf')
graph[t][f] = float('inf')
# 간선 제거 후 다시 최단 거리 계산
parade_cost = minimum_cost_graph(graph)
# 모든 정점쌍 (i, j)에 대해 비교
for i in range(N):
for j in range(i + 1, N):
# 원래보다 최단 거리가 증가했거나 연결이 끊겼다면, 해당 간선이 사용되었음
if origin_cost[i][j] < parade_cost[i][j] or parade_cost[i][j] == float('inf'):
result[idx] += 1
# 제거한 간선 복원
graph[f][t] = time
graph[t][f] = time
# 결과 출력
print(*result)2️⃣ 다익스트라 * N번
import heapq
import sys
input = sys.stdin.readline
INF = float('inf')
# 입력: 정점 수 N, 간선 수 M
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
edges = []
# 그래프 구성 및 간선 정보 저장
for _ in range(M):
u, v, w = map(int, input().split())
graph[u].append((v, w))
graph[v].append((u, w))
edges.append((u, v, w))
# dist[i][j]: i → j 최단 거리
# count[i][j]: i → j 최단 경로 개수
dist = [[INF] * N for _ in range(N)]
count = [[0] * N for _ in range(N)]
# 모든 정점에서 다익스트라 수행
for start in range(N):
dist[start][start] = 0
count[start][start] = 1
hq = [(0, start)]
while hq:
cost, cur = heapq.heappop(hq)
if cost > dist[start][cur]:
continue
for to, w in graph[cur]:
new_cost = cost + w
# 더 짧은 경로 발견
if new_cost < dist[start][to]:
dist[start][to] = new_cost
count[start][to] = count[start][cur]
heapq.heappush(hq, (new_cost, to))
# 동일한 거리 → 경로 추가
elif new_cost == dist[start][to]:
count[start][to] += count[start][cur]
# 각 간선이 "필수적으로" 사용되는 최단 경로 수 계산
result = []
for u, v, w in edges:
cnt = 0
for i in range(N):
for j in range(i + 1, N):
if dist[i][j] == INF:
continue
# (u, v) 경유 경로가 유일한 최단 경로일 때만 카운트
cond1 = dist[i][j] == dist[i][u] + w + dist[v][j] and \
count[i][j] == count[i][u] * count[v][j]
cond2 = dist[i][j] == dist[i][v] + w + dist[u][j] and \
count[i][j] == count[i][v] * count[u][j]
if cond1 or cond2:
cnt += 1
result.append(cnt)
# 결과 출력
print(*result)🚀 시행착오 했던 부분 - 초반 접근을 플로이드-워셜로 접근
-> 한 정점에서 모든 정점으로 가기 때문에 플로이드-워셜로 해결하려고 시도함.
-> 플로이드-워셜로 테스트 케이스는 모두 통과 했지만 시간 초과 발생
-> 플로이드-워셜의 시간 복잡도는 N^3 인 데, 간선을 지우면서 매번 플로이드-워셜로 계산하다보니 M * N^3으로 더 복잡하고 느려짐
-> 한 정점에서 다른 정점으로의 최단 거리를 구하는 다익스트라( O(MlogN) )를 N번 수행하면 보다 더 빠르게 연산 가능
🧐 그럼 언제 플로이드-워셜을 쓰고, 또 다익스트라 * N번을 써야하나?
GPT에게 물어봤더니
✅ 언제 플로이드 워셜을 써야 할까?
• N이 작고 (N ≤ 400) 모든 정점 쌍 사이의 거리나 경로 정보가 필요할 때
• 간선에 음수 가중치가 있는 경우
• 그래프가 조밀한(fully connected) 경우
• 빠르게 코드 짜고 싶을 때 (초단순 구현)
✅ 언제 다익스트라 N번이 더 나을까?
• 희소 그래프일 때 (간선 M이 적을 때)
• N이 크고, M도 큰 경우 (N ≤ 5000~10000, M ≤ 수십만)
• 양의 가중치만 있을 때
• 한 정점에서 다른 모든 정점까지 구하는 문제 다수일 때
• 경로 개수, 경로 복원 등 디테일한 정보가 필요할 때
라고 하는데, 이번 문제에서 N이 100이하로 충분히 작았지만, 간선 개수만큼 연산이 반복되었던 문제기 떄문에 뭔가 어떤 알고리즘을 언제써야한다는 명백하게 정하기 어렵지 않을까 생각했다.
언제 뭘 써야하나를 고민하기보다 두 방식 모두 알아두고, 모든 정점에 대한 최소 거리를 연산해야할 때 충분히 작은 케이스라고 판단되면 플로이드-워셜이 상대적으로 빨리 구현가능하니 시도해보고, 추후 다익스트라를 사용하는 방향으로 빠르게 전환하는 게 올바른 방향이지 않을까 생각한다.
