[알고리즘/BFS] 1389번 : 케빈 베이컨의 6단계 법칙 - python

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

 

 

---

• 문제
• 소요시간: 47분 13초

---

• 설계하기(접근방법) 

1. 입력받기

양방향 그래프니, 그래프를 초기화 할 때 양쪽을 초기화 해준다

 

2. 구현하기

시작지점이 고정된 BFS와 달리 모든 시작점에서 BFS를 순회해야하니, for문을 통해 각 BFS를 실행해주어야 한다.

 

최단거리 BFS를 구현한 후에 for문을 통해 1번부터 N번까지 실행하면서,

거리의 합을 bacon_map list에 저장한다

 

3. 출력하기

bacon_map list의 sum 최소값 중에서 가장 작은 사람의 수를 출력한다

 

 

---

• 코드(출력)

from collections import deque

n , m = map(int, input().split())

graph = [[] for _ in range(n + 1)]
bacon_map = []

# graph 지도 만들기
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)


def bfs(start):
    visited = [0 for _ in range(n + 1)]
    q = deque()
    q.append(start)

    while q:
        x = q.popleft()
        for i in graph[x]:
            if i != start:
                if visited[i] == 0 or visited[x] + 1 < visited[i]:
                    visited[i] = visited[x] + 1
                    q.append(i)

    bacon_map.append(sum(visited))
    
for i in range(1, n + 1):
    bfs(i)

small = min(bacon_map)

for i in range(m):
    if bacon_map[i] == small:
        print(i + 1)
        break

---

• 얻어갈 부분

1. 각 지점에서 for문을 통해 순회하면 되는데 visited list를 n*n을 선언해서 구현하다 실패했다. 문제의 예시를 시뮬레이션하고 주석에 적으면서 구현해보자