[모각코] 220720 Today I Learned

우와 모각코 어게인

 

 

<백준 1389번 - 케빈 베이컨의 6단계 법칙>

 

알고리즘 문제 안 푼 지 오래 됐더니.. 문제 보고 바로 그래프 문제구나 라고 떠올리는데 오래 걸렸다.

그래프로 푸는 건 바로 그려지긴 했는데 bfs로 풀어야겠다는 생각이 바로 들진 않았다.

 

 

자기 자신과의 단계는 0이므로 이를 표현하기 위해 visited의 초기값을 -1로 지정하였다.

bfs함수를 호출하면 해당 사람(?)의 visited 값을 0으로 바꾸어준다. (자기자신)

한 번 방문할 때마다 이전에 방문한 친구의 단계에서 1을 더해준다.

 

케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합이므로

bfs 함수 종료 전에 sum(visited)를 구해주었다.

그리고 함수에서 빠져나온 뒤 이를 ans 리스트에 넣는다.

 

모든 유저에 대해서 bfs 함수를 실행한 후에 케빈 베이컨 수가 가장 작은 사람의 인덱스를 출력하면 된다.

 

ans 리스트 초기 설정할 때 인덱스를 맞춰주기 위해서 0번 인덱스 값으로 양의 무한대를 넣어주었다.

(ans의 최솟값을 출력해야 하므로)

양의 무한대값은 어떻게 쓰는지 까먹어서 구글링했다.

https://da-nyee.github.io/posts/python-infinity/

[Python] 양의 무한대(inf), 음의 무한대(-inf) 표시

 

 

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

def bfs(i):
    visited = [-1 for _ in range(n+1)]
    q = deque()
    q.append(i)
    visited[i] = 0
    while q:
        w = q.popleft()
        for j in friend[w]:
            if visited[j] == -1:
                visited[j] = visited[w] + 1
                q.append(j)
    return sum(visited)

n, m = map(int, input().split())
friend = [[] for _ in range(n+1)]
ans = [float("inf")]

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

for i in range(1, n+1):
    ans.append(bfs(i))

print(ans.index(min(ans)))