DP
백준 관련 문제
벨만–포드 vs 플로이드–워셜
- 벨만–포드(Bellman–Ford): “단일 시작점 최단거리 + 음수 간선/음수 사이클 판정”
- 플로이드–워셜(Floyd–Warshall): “모든 정점 쌍 최단거리(All-Pairs) 한 번에”
가장 중요한 차이: “시작점 개수”
벨만–포드
- 시작점이 하나(혹은 소수)일 때 최적
- 예: “1번에서 모든 도시까지”, “S에서 모든 정점까지” 같은 문제.
플로이드-워셜
- 시작점이 모든 정점인 문제에 적합
- 예: “모든 i→j 최단거리”, “i에서 j로 가는 최단거리 질문이 여러 번” 같은 문제.
데이터 구조 관점: “간선 리스트 vs 행렬”
벨만-포드
- 입력 형태가 보통 간선 리스트: (a,b,c)
- dist 배열 하나로 충분.
플로이드-워셜
- N×N 거리 행렬이 기본.
- dist[i][j] 초기화가 중요:
- dist[i][i] = 0
- 간선 있으면 dist[a][b] = min(dist[a][b], c)
- 없으면 INF
음수 간선 / 음수 사이클 처리 능력
벨만-포드
음수 사이클 판별 가능
- 핵심: n-1번 완화 후에도 더 줄어들면 음수 사이클
- 단, “시작점에서 도달 가능한 사이클”만 체크하려면 dist[a] != INF 조건 필요
코드 형태 (벨만–포드)
import sys
input = sys.stdin.readline
INF = 10**18
n, m = map(int, input().split())
edges = []
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((a, b, c))
dist = [INF] * (n + 1)
dist[1] = 0 # 시작점
# 1️⃣ n-1번 완화 (최단거리 계산)
for _ in range(n - 1):
updated = False
for a, b, c in edges:
if dist[a] != INF and dist[b] > dist[a] + c:
dist[b] = dist[a] + c
updated = True
if not updated: # 더 이상 정보 전달 없음
break
# 2️⃣ 음수 사이클 검사
has_neg_cycle = False
for a, b, c in edges:
if dist[a] != INF and dist[b] > dist[a] + c:
has_neg_cycle = True
break
# 3️⃣ 출력
if has_neg_cycle:
print(-1)
else:
for i in range(2, n + 1):
print(dist[i] if dist[i] != INF else -1)
코드 형태 (플로이드–워셜)
import sys
input = sys.stdin.readline
INF = 10**18
n, m = map(int, input().split())
# 거리 행렬 초기화
dist = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dist[i][i] = 0
# 간선 입력
for _ in range(m):
a, b, c = map(int, input().split())
dist[a][b] = min(dist[a][b], c) # 중복 간선 처리
# 플로이드–워셜
for k in range(1, n + 1):
for i in range(1, n + 1):
if dist[i][k] == INF:
continue
for j in range(1, n + 1):
if dist[k][j] == INF:
continue
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
# 결과 출력 예시 (i → j)
for i in range(1, n + 1):
for j in range(1, n + 1):
print(dist[i][j] if dist[i][j] != INF else 0, end=" ")
print()