[BOJ][Python]1389번 풀이

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

1389번: 케빈 베이컨의 6단계 법칙

from collections import deque
import sys
ssr = sys.stdin.readline

def sol(p):
    visited[p] = True
    q=deque([])
    q.append((p,0))
    b_num=0
    while q:
        a = q.popleft()
        b_num += a[1]
        for i in edges:
            if i[0] == a[0] and visited[i[1]] == False:
                q.append((i[1], a[1]+1))
                visited[i[1]] = True
            elif i[1] == a[0] and visited[i[0]] == False:
                q.append((i[0], a[1]+1))
                visited[i[0]] = True
    return b_num

n,m = map(int, ssr().split())
edges = [list(map(int, ssr().split())) for _ in range(m)]
idx = []
for i in range(1,n+1):
    visited = [False for _ in range(n+1)]
    idx.append(sol(i))
ans = idx.index(min(idx))+1
print(ans)

정말 어처구니 없는 실수를 했습니다. 아주 예전에 그랬던 적이 한 번 있었는데 조건문을 작성하다보면 자기도 모르게 조건연산자를 대입연산자 대신 쓰는 일이 가끔 있는데요. 오늘도 그렇게 해놓고 왜 자꾸 값이 이상하게 나오나 한참을 고민하면서 디버깅을 하다보니 방문 처리가 제대로 안되는 것을 발견해서 무슨 일인가 싶었더니 등호를 두개나 썼더군요. 너무 오랜만이라 이런 실수가 있었는지 쉽게 찾기도 힘들었습니다.

 

문제의 접근은 일반 bfs와 동일합니다. 다만 그걸 여러번 반복해야할 뿐이에요. bfs 문제를 많이 풀어본 분들은 크게 어려움 없이 푸셨을 것 같습니다. 기본적인 부분은 bfs와 다르지 않으니 해당 부분은 간략하게 설명하겠습니다. 일단 케빈 베이컨 숫자를 구하기 위해서는 처음에 입력했던 노드가 각 노드에 최단거리로 도착하는 방법을 모두 더해야 하죠. 따라서 전에 했던 것처럼 큐에 자료를 집어넣을 때 노드에 방문할 때 마다 1씩 증가하는 숫자를 함께 넣습니다. 해당 숫자가 방문 횟수이자 거리가 되겠죠. 또한 방문 여부를 체크하기 때문에 똑같은 노드는 다시 큐에 저장될 일이 없기에 사실상 한 번 입력되면 끝이라고 봐도 무방합니다. 따라서 큐에서 자료를 빼낼 때 마다 방문 횟수를 b_num에 더해주면 반복문이 끝났을 때는 처음에 입력했던 노드의 케빈 베이컨 숫자가 완성되어 있는 것입니다. 그걸 반환해서 마지막에는 최솟값의 인덱스에 +1을 해서 출력해주면 됩니다(어차피 sol은 1부터 실행하도록 반복문이 작성되어 있기 때문).