[BOJ 1389] 케빈 베이컨의 6단계 법칙 (Python3)

www.acmicpc.net/problem/1389

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

 

from collections import deque
 
N, M=map(int, input().split())
graph=[set() for _ in range(N+1)]
visited=[False]*(N+1)
result=0
array=[]
 
for _ in range(M):
    a,b=map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)
 
def bfs(i):
    result=0
    queue=deque()
    queue.append((i,0))
    visited[i]=True
    while queue:
        pos, cnt=queue.popleft()
        result+=cnt
        for i in graph[pos]:
            if not visited[i]:
                queue.append((i,cnt+1))
                visited[i]=True
    return result
 
for i in range(1,N+1):
    visited=[False]*(N+1)
    array.append(bfs(i))
 
print(array.index(min(array))+1)

 

문제들이 잘 안풀려서 힘든 날이었다.. 원래 "치즈" 풀려고 했는데 문제 조건을 잘못 이해한채로 몇시간째 고민하는 바람에... 헤헿 그 문제는 들여다보기 싫어서 별표만 쳐놈 ㅎㅎ

암튼.. 이 문제!는 첨엔 DFS로 탐색해서 count 값을 증가시켜 저장하는 형태로 풀려 했다가.. 그렇게 했는데 답이 틀린 걸 알고 그 방법은 깊이 탐색하는 방법이기 때문에 돌아서 값을 체크하는 법임을 깨달았다.. 즉 1-4에서 거리가 1인데, DFS에서는 3으로 체크한다는것!

아 그래서 BFS구나 깨달았다!

(사람의 번호, 카운트 값)을 저장해서 인접한 사람을 만날때마다 카운트+1 해주고 그 큐에 담긴 모든 아이템에 대해 그 카운트 값을 더해서 케빈 베이컨의 수를 리턴한다.

 

 

--아 구글링해보니 DFS로 푼사람들도 많네 ^&^;;

 

아래 소스코드 출처: hy38.github.io/BOJ-1389

BOJ 1389 - 케빈 베이컨의 6단계 법칙

이 분꺼 참조해 보자면, DFS로 각 지점 간 최단거리를 구하는 방식을 썼다.

DFS로 각 지점 간 최소 거리를 구해준다. DFS로 재귀 호출할 때 c라는 변수를 이용해 카운트를 해준 뒤, min 값을 비교한다. 

DFS로 경우의 수 찾는 것과 비슷한 패턴이다.!