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

[문제 URL]

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

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

---

[풀이해설]

이 문제는 BFS 개념을 공부하기에 좋은 문제이다.

BFS는 현재노드와 바로 연결되어 있는 노드를 큐에 넣는다.

 

(1) 각 노드마다 연결된 노드를 구해서 연결관계 리스트를 만든다.

(2) BFS를 이용하여 시작점에서 각 노드로 도달하는데 간선의 개수들의 합을 구한다. (각 노드별 케빈베이컨 수)

(3) 가장 작은 케빈 베이컨 수를 갖는 사람을 구한다.

-> 해시테이블로 나타냈다. (KEY값: 사람번호, VALUE값: 시작점(KEY값)에서 얻은 케빈 베이컨 수)

-> VALUE를 기준으로 오름차순 정렬

-> 동일한 VALUE를 가질 때 KEY가 가장 작은 순으로 정렬.

 

 

[BFS를 활용한 방법 순서]

시작점 노드가 1번일때만을 나타내봤다.

---

[Python3]

 

import sys
from collections import deque
connections=None
visited=None
q= deque()

def bfs():
    global visited, connections
    edge_cnt=0 # start와 연결된 간선의 개수
    while q:
        p, cnt=q.popleft()
        # p(1,2,3,..,N)가 아직 방문이 안한 상태인가?
        if not visited[p-1]:
            visited[p-1]=True
            edge_cnt+=cnt#edge_cnt에 cnt를 더한다.
            
            # p와 연결된 노드x가 아직 방문하지 않은 상태인가?
            for x in connections[p-1]:
                if not visited[x-1]:
                    q.append((x, cnt+1)) #큐에 추가
                    
    #큐가 비어있으면 edge_cnt를 리턴
    return edge_cnt    

def main():
    global connections, visited
    
    # N: 유저의수 (노드개수)
    # M: 친구관계수 (노드간 연결관계)
    N, M= map(int, sys.stdin.readline().split())

    #각 노드별 친구관계리스트 입력
    connections=[[] for _ in range(N)] #N명의 연결관계 리스트

    # f1과 f2는 친구이므로
    # f1의 친구관계 리스트에 f2를 추가
    # 반대로, f2의 친구관계 리스트에 f1을 추가
    for _ in range(M):
        f1, f2= map(int, sys.stdin.readline().split())
        connections[f1-1].append(f2)
        connections[f2-1].append(f1)

    kevin_nums={} #각 노드별 케빈베이컨 수를 딕셔너리로 나타냄.
    # BFS를 이용하여, 각 노드별 케빈베이컨 수를 구한다.
    for start in range(1,N+1):
        visited=[False]*N #방문리스트 visited 초기화
        q.append((start,0)) #start: 1,2,3,...,N
        result=bfs() # start에서 시작해서 각 노드에 도착한 간선수의 합
        kevin_nums[start]=result
        
    # kevin_nums의 value를 기준으로 오름차순 정렬
    # 동일한 value를 가질때 key값(사람번호)이 작은걸  우선시한다.
    kevin_nums=sorted(kevin_nums.items() , key=lambda x: (x[1], x[0]))
    print(kevin_nums[0][0])
    
if __name__=='__main__':
    main()

 

[채점 결과]

---

[Java]