백준 1389 (python) 케빈 베이컨의 6단계 법칙

BFS

bfs로 풀었음

 

 

 

플로이드 와샬 풀이가 바로 떠올라서 최대한 bfs로 풀려고 노력했다.

 

즉 어느 하나의 노드를 기준으로 탐색하게 되면,

해당 노드로부터 다른 노드까지의 depth를 bfs로 탐색해가며 구할 수 있다.

 

 

시작이되는 어떤 노드를 queue(이하 q로 부름) 에 삽입한다.

q를 pop해 그 노드와 인접한 (adj, copy 배열이 1), 방문하지 않은 노드를 그 다음으로 선정한다.

 

이때 depth를 1씩 증가한다. 

이는 시작노드로부터의 depth가 현재 pop한 x(현재 노드)까지의 depth보다 1이 증가함을 의미한다.

 

다른 말로, 0-1-2 순으로 노드가 있으면, 0-2까지의 depth는 0-1까지의 depth + 1이다.

 

그렇게 해서 q가 비었다면, 즉 모든 노드를 탐색했다면

저장된 2차원 배열의 각 행에 있는 열의 총합을 구해주었다.

(0번째 행의 합 = 0번 노드의 케빈 베이컨의 수)

 

 

조건에 모든 노드가 연결되었다고 나와있기 때문에 q가 비면 모든 노드를 탐색한 것이다.

 

 

from collections import deque
from copy import copy
import queue


n, m = map(int, input().split())
adj = [[0]*n for i in range(n)]
copy = [[0]*n for i in range(n)]
queue = deque()


def bfs(a):
    queue.append(a)
    visit = [0 for i in range(n)]
    while queue:
        x = queue.popleft()
        visit[x] = True
        for i in range(0, n):
            if copy[x][i] == 1 and not visit[i]:
                copy[a][i] = copy[i][a] = copy[x][a] + 1
                visit[i] = True
                queue.append(i)

    return sum(copy[a])


for _ in range(m):
    a, b = map(int, input().split())
    adj[a-1][b-1] = 1
    adj[b-1][a-1] = 1

copy = adj
ans = [[0]*n for i in range(n)]
for i in range(0, n):
    ans[i] = bfs(i)

print(ans.index(min(ans))+1)

 

 

파이썬으로 풀어보았다! 

언어 변경할 결심...