[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙

[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙

 

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

 

 

문제를 보고 친구 관계가 연결되어 있고, 관계를 하나하나 따라 들어가 몇단계인지 찾는다는 부분에서 이거 뭔가 탐색 문제일 것 같은데..! 라는 생각이 들었다. 이어서 최단 경로의 단계를 찾는다는 부분에서 이건 bfs다 라는 생각으로 이어졌다.

 

어떤 유형의 문제인지 알았으니 이제 입력 받은 데이터를 어떻게 넣어서 bfs를 통해 풀면 될것 같은데, 어떤 자료구조로 넣지? 생각하다가 그래프의 두가지 표현 방식인 1) 인접 리스트(1: 2, 4, 5 / 2: 1, 5 / ...) 2) 인접 행렬(arr[i][j]로 표현)이 떠올랐다. 그중에서 나는 특정 점에 연결된 점들을 찾는 방식을 많이 사용할 거니까 1) 인접 리스트를 선택!

 

구현은 간단했다. 간단하게 bfs 구현 하는 부분만 적어보면 아래와 같다.

ex) 2에서 5까지

queue.push(2)
2.visited = true

while len(queue) != 0:
  a = queue.pop()

  if a가 찾던 5라면:
      최소 단계임! 단계 저장
      break

  for a에 인접한 값 b들에 대하여:
      if b.visited = true:
          continue
      else:
          queue.push(b, a의 단계 + 1)
          b.visited = true

이제 이것을 1인 경우 2, 3, 4, 5와의 단계 수를 구하고, 2인 경우 1, 3, 4, 5와의 단계 수를 구하고.. 이런식으로 for문을 통해 처리해주면 된다.

 

bfs를 구현하는 과정에서 변수명만 queue라고 적어두고 바보같이 그냥 pop메서드를 썼다. pop을 하면 가장 마지막 index가 pop되는 건데 너무 오랜만에 bfs문제를 풀어서 그런지 pop을 쓰고 오른쪽에서 pop되는 거겠지~라고 생각하고 있었던 것 같다. 계속 헤맸는데 알고보니 이 문제.. 좀더 꼼꼼히 풀어야겠다..

 

내 코드는 아래와 같다.

 

# BaekJoon 1389 케빈 베이컨의 6단계 법칙
from collections import deque

if __name__ == "__main__":

    answer = [0, 100000]
    N, M = map(int, input().split())
    arr = {}

    # 초기화, 인접 리스트
    for i in range(M):
        a, b = map(int, input().split())
        if a in arr:
            arr[a].append(b)
        else:
            arr[a] = [b]
        if b in arr:
            arr[b].append(a)
        else:
            arr[b] = [a]

    for i in range(N):
        tmp_result = 0
        for j in range(N):
            if i == j:
                continue
            visited = {}
            queue = deque()
            for key in arr.keys():
                visited[key] = False

            # 초기값 push
            queue.append([list(arr.keys())[i], 0])
            visited[list(arr.keys())[i]] = True

            # 큐가 빌때까지 반복
            while len(queue) != 0:
                value = queue.popleft()

                # 최단 경로 찾으면 단계 추가 후 break
                if value[0] == list(arr.keys())[j]:
                    tmp_result = tmp_result + value[1]
                    break

                # 이어서 연결된 다음 친구로
                for k in arr[value[0]]:
                    if visited[k] is False:
                        queue.append([k, value[1] + 1])
                        visited[k] = True

        # i번이 케빈 베이컨의 수가 가장 작은지 확인
        # 작은게 여러개라면 숫자가 작은걸로
        if tmp_result < answer[1]:
            answer[0] = list(arr.keys())[i]
            answer[1] = tmp_result
        elif tmp_result == answer[1]:
            if list(arr.keys())[i] < answer[0]:
                answer[0] = list(arr.keys())[i]

    print(answer[0])