(BOJ #1389🔴) 케빈 베이컨의 6단계 법칙

학습 키워드

그래프 탐색 (BFS)

 

핵심 포인트

1. adj (인접 리스트) 사용
2. 시작점
3. visit 배열
4. dist(최단거리) 배열
5. Queue

 

개선해야할 점

복잡하게 생각하지 말고, 최대한 심플한 코드를 작성하자.

그리고 먼저 손과 머리로 풀이가 완료된 다음에 코딩 하자.

 

 

🔴풀이 순서🔴

1. adj (인접 리스트) 사용
2. 시작점을 기준 (0~N-1 모두 탐색)
3. 시작점을 queue에 append
4. queue.pop
5. <⭐️1⭐️> pop한 adj index 확인
6. 확인한 adj index는, queue에 들여보내기 전, 먼저 확인!!
7. <⭐2⭐️> 확인 >> adj 순서대로, True; pass, False: queue추가 & 직전 pop한 index의 dist(최단거리) + 1

 

 

새로 배운 개념

• adj 인접배열
  • 그래프 문제에서 사용

 

• Deque (데크)
  • Python 에서 사용하는 Queue

 

 

 

그림 풀이

알고리즘 이해 & 풀이

 

테스트케이스 이해

 

 

 

 

 

코드

• tutor 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = list(map(int, input().split()))

# 인접리스트
adj = [[] for _ in range(N)]

for _ in range(M):
  u, v = list(map(int, input().split()))
  adj[u - 1].append(v - 1)
  adj[v - 1].append(u - 1)

min_kevin_bacon = 1e9
min_person = -1

for startPoint in range(N):
  # startPoint를 시작점으로 하는 BFS 
  # 각 노드까지의 최단거리를 구해서 다 합치기
  visit = [False] * N
  dist = [-1] * N

  visit[startPoint] = True
  dist[startPoint] = 0
  queue = deque([startPoint])

  while len(queue) != 0:
    q = queue.popleft()

    for v in adj[q]:
      if not visit[v]:
        queue.append(v)
        visit[v] = True
        dist[v] = dist[q] + 1
  
  if min_kevin_bacon > sum(dist):
    min_kevin_bacon = sum(dist)
    min_person = startPoint + 1

print(min_person)

 

 

레퍼런스

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