[파이썬] 백준 10159 저울

시간이 아주 오래 걸렸지만 정답이 되었다. 두 가지 경우로 나누어준 후 bfs 를 돌려주었다. 플로이드 워셜 알고리즘을 사용하는 문제라고 한다.

import sys
from collections import deque
 
n = int(input())
m = int(input())
 
k = [ ]
 
for i in range(m):
    k.append(list(map(int,sys.stdin.readline().split(" "))))
 
k = list(sorted(k))
 
 
def check(k,num,n):
 
    visited = [0] * (n+1)
 
    visited[0] = 1
    visited[num] = 1
 
    queue = deque()
 
    # i 로 시작하는 걸로 반복문 돌리기
 
    for i in range(0,len(k)):
        if k[i][0] == num:
            queue.append(k[i][1])
 
    while queue:
        x = queue.popleft()
 
        visited[x] = 1
 
        for i in range(0,len(k)):
            if k[i][0] == x and visited[k[i][1]] == 0:
                queue.append(k[i][1])
 
 
# i 로 끝나는 걸로 반복문 돌리기
 
    queue1 = deque()
 
    for i in range(0,len(k)):
        if k[i][1] == num:
            queue1.append(k[i][0])
 
    while queue1:
        x = queue1.popleft()
 
        visited[x] = 1
 
        for i in range(0,len(k)):
            if k[i][1] == x and visited[k[i][0]] == 0:
                queue1.append(k[i][0])
 
    print(visited.count(0))
 
for i in range(1,n+1):
    check(k,i,n)