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

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

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

문제 한줄 이해

-N명의 사람이 주어지고 친구 관계 M개가 주어 졌을때 각 사람이 다른사람을 몇번의 건너건너를 해서 아는지 총합을 구하기(본인과 김사또가 있을때 한번에 아는 사이면 1단계 친구, 내가 아는 친구의 친구(김사또)면 2단계)

 

생각난 풀이

1번째 방법: 1~N번 사람들을 각각 BFS를 통해 다른 사람들과 몇단계로 이루어져있는지 확인을 하는데 이때 그냥 큐가 아닌 우선순위 큐를 사용했다. 

이유는 다음 친구를 탐색할때 (단계+1, 연결된 친구)를 통해 몇단계로 이루어져 있는지 파악하기 위함이다.

import sys
import heapq
n, m = map(int,sys.stdin.readline().split())
graph = [[0 for i in range(n+1)] for i in range(n+1)]

for i in range(m):
    x,y = map(int,sys.stdin.readline().split())
    graph[x][y] = 1
    graph[y][x] = 1
    
def bfs(cnt,start):
    global result
    # 깊이가 낮은 순으로 탐색을 먼저 진행해야 하기 때문에 heap이용
    hq = []
    heapq.heappush(hq,(cnt,start))
    visited[start] = True
    
    while hq:
        cnt,nowv = heapq.heappop(hq)
        print(cnt,nowv)
        result += cnt
        for i in range(1,n+1):
            if graph[nowv][i] ==1 and visited[i] == False:
                visited[i] = True
                # 연결된 친구들 heap에 담고 1단계 증가
                heapq.heappush(hq,(cnt+1,i))

# 각 사람들의 케빈 베이턴 값을 담을 리스트
ans = []
for i in range(1,n+1):
    # 1번, 2번 , ....확인 할때마다 visited와 result 값 초기화
    visited = [False]*(n+1)
    result = 0
    bfs(0,i)
    # 함수 실행 끝나면 베이컨 값 담기
    ans.append(result)
print(ans.index(min(ans))+1)