[BOJ] 백준 11562번 문제 풀이 (Python)

1. 문제 풀이

플로이드-워셜 알고리즘을 이용하여 문제를 풀었습니다.

• $graph[a][b]$: a에서 b로 가기위해 바꿔야하는 일방통행 길의 최소 갯수
• $u,v, b$의 형태로 길에 대한 정보가 주어질 때,
  • $b$ 가 1일 경우 $graph[u][v]=graph[v][u] = 0$
  • $b$ 가 0일 경우 $v$ → $u$ 로 가려면 일방통행 길을 1번 바꿔야합니다.
    • $graph[u][v] = 0$
    • $graph[v][u] =1$
• 나머지 길의 경우 플로이드-워셜 알고리즘을 이용해서 구하였습니다.

2. 코드

import sys
INF = int(1e14)
def input(): return sys.stdin.readline().rstrip()

n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    if c:
        graph[a][b] = 0
        graph[b][a] = 0
    else:
        graph[a][b] = 0
        graph[b][a] = 1

for k in range(1,n+1):
    for i in range(1, n+1):
        for j in range(1,n+1):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

for i in range(n+1):
    graph[i][i] = 0

for _ in range(int(input())):
    s, e = map(int, input().split())
    print(graph[s][e])