boj.kr/1389 케빈 베이컨의 6단계 법칙 (silver1) 파이썬 풀이

#풀이1

bfs 방식으로 각 사람사이 최단거리를 구하고 그 합을 리스트에 저장해 합계, 사람번호 오름차순으로 정렬해 첫번째 사람의 번호를 출력

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(M)]

from collections import deque
def bfs(n):
    dq = deque()
    dq.append(n)

    while dq:
        cur = dq.popleft()
        if cur == n and adj[n-1][n-1] == 1 :
            break
        adj[n-1][n-1] = 1
        for i in range(M):
            if board[i][0] == cur and not adj[n-1][board[i][1]-1] :
                adj[n-1][board[i][1]-1] = adj[n-1][board[i][0]-1] + 1
                dq.append(board[i][1])
            if board[i][1] == cur and not adj[n-1][board[i][0]-1] :
                adj[n-1][board[i][0]-1] = adj[n-1][board[i][1]-1] + 1
                dq.append(board[i][0])

tot_list = []
for i in range(1, N+1):
    adj = [[0] * N for _ in range(N)]
    bfs(i)
    tot_list.append([i, sum(adj[i-1])])

tot_list.sort(key = lambda x : (x[1], x[0]))
print(tot_list[0][0])

 

# 풀이2 - 플로이드-워셜만 활용

1. 일차 인덱스를 시작번호, 이차 인덱스를 도착 번호로 하고 요소값을 최소거리로 갖도록 graph 배열을 초기화

2. 플로이드-워셜 알고리즘을 사용하여 graph의 모든 요소값을 최소거리로 저장

3. graph의 일차 인덱스를 순회하면서 합계가 최소값인 인덱스를 저장

4. 저장한 인덱스를 출력

N, M = map(int, input().split())
graph = [[1e9]*(N+1) for _ in range(N+1)]

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

for _ in range(1, N+1):
    graph[_][_] = 0
    graph[_][0] = 0

for k in range(1, N+1):
    for s in range(1, N+1):
        for e in range(1, N+1):
            if graph[s][e] > graph[s][k] + graph[k][e]:
                graph[s][e] = graph[s][k] + graph[k][e]

min_sum = 1e9
ans = 0
for i in range(1, N+1):
    if min_sum >= sum(graph[N+1-i]):
        min_sum = sum(graph[N+1-i])
        ans = N+1-i

print(ans)

 

플로이드 워셜 알고리즘을 구현할 때 사용하는 그래프에서 자기자신에 대한 거리값을 0으로 저장하는 것을 잊지 않도록 주의해야 한다.