[BOJ / 백준] 1389 케빈 베이컨의 6단계 법칙 (S1 / BFS) - Python

링크

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

 

 

 

 

문제 해석

A와 B가 소개를 통해서 알 수 있는 거리를 베이컨 거리라고 한다.

 

A와 B가 직접 아는 사이라면 거리가 1이고,

A와 C가 직접 아는 사이이고, B와 C가 직접 아는 사이라면 A와 C는 거리가 2이다.

 

n명의 사람이 주어졌을 때 모든 사람과 가장 베이컨 거리의 합이 짧은 사람을 구하라.

 

 

 

입력

첫 번째 줄 : n, m
  n : 유저수
  m : 친구 관계 수

 

 

출력

베이컨 거리가 가장 짧은 사람의 번호 

단 베이컨 거리가 동일한 사람이 있는 경우 번호가 가장 작은 사람이 정답

 

 

 

 

풀이 & 코드 해석

주어지는 사람들간의 관계(간선)은 가중치 없이 모두 균등합니다.

 

균등한 가중치를 가지는 그래프에서 최단 거리를 찾을 때는 BFS를 사용할 수 있습니다.

 

 

A라는 사람으로부터 나머지 모든 사람으로까지 베이컨 거리를 먼저 구해봅시다.

 

문제 조건에서 모든 사람은 이어져 있다고 하였으니, BFS를 사용한다면 다른 모든 사람들에게 방문할 수 있으며, 각 사람에게 도달하는데 얼마나 걸리는지도 알 수 있을 것입니다.

 

따라서 모든 사람을 한 번씩 BFS의 출발지로 지정한 후, 나머지 사람에게 도착하는데 걸리는 시간을 합한 결과를 비교하여 가장 거리 합이 작은 사람을 정답으로 출력하면 됩니다.

  

 

 

 

코드

from collections import deque


def bfs(s):
    global ans, ans_cnt, n
    dis = [-1] * (n + 1)
    dis[0] = 0

    q = deque()

    q.append(s)
    dis[s] = 0

    while q:
        px = q.popleft()

        for nxt in graph[px]:
            if dis[nxt] != -1:
                continue

            dis[nxt] = dis[px] + 1
            q.append(nxt)

    total = sum(dis)
    if total < ans_cnt:
        ans = s
        ans_cnt = total
    elif total == ans_cnt:
        if s < ans:
            ans = s


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

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

for _ in range(m):
    s, e = list(map(int, input().split()))

    graph[s].append(e)
    graph[e].append(s)

ans = int(1e9)
ans_cnt = int(1e9)
for s in range(1, n + 1):
    bfs(s)

print(ans)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java