[Python] 저울 - 백준 (최단경로)

해당 글은 백준 10159번 '저울' 문제를 다룬다.

문제

https://www.acmicpc.net/problem/10159

10159번: 저울

 

설명

해당 문제는 최단 경로 찾기 문제 중 플로이드-워셜 알고리즘을 활용하여 해결할 수 있다.

여기서 그래프는 이동 가능할 때 True, 이동 불가능 할 때 False로 만들었다.

플로이드-워셜 알고리즘으로 i->j로 이동할 때, k를 거쳐서 이동가능한 경우도 True로 변경해준다.

마지막 출력으로 i->j로 이동 불가능하고, j->i로도 이동 불가능한 경우에만 카운트하면 된다. 

 

코드

n = int(input())
m = int(input())

# True: 이동O, False: 이동X
graph = [[False] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):  # 현재 위치
    graph[i][i] = True

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = True

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if graph[i][k] and graph[k][j]:  # k를 거쳐서 i->j로 이동할 수 있을때
                graph[i][j] = True

for i in range(1, n + 1):
    count = 0
    for j in range(1, n + 1):
        if not graph[i][j] and not graph[j][i]:  # 둘다 0일 경우
            count += 1
    print(count)