JinWoo Kim

백문이 불여일견, 백견이 불여일행.

3 minute read

1. 케빈 베이컨의 6단계 법칙

  • 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.

  • 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

  • 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

    • 천민호는 이강호와 같은 학교에 다니는 사이이다.
    • 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다.
    • 최백준과 김선영은 같이 Startlink를 창업했다.
    • 김선영과 김도현은 같은 학교 동아리 소속이다.
    • 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다.
    • 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

  • 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

  • 오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

    • 예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

    • 1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

    • 2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

    • 3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

    • 4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

    • 마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

    • 5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

  • BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다.
  • 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다.
  • 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다.
  • A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다.
  • 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다.
  • 또, 모든 사람은 친구 관계로 연결되어져 있다.
  • 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

출력

  • 첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다.
  • 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

개념정리

  • 그래프를 통해 푸는것은 알겠지만, 그래프 탐색으로 풀어보려 시도했으나 실패했다.

  • 따라서 알지 못하는 새로운 개념이 사용된것으로 판단하고, 어떤 알고리즘이 사용되었는지 확인했다.

플로이드-와샬 알고리즘

  • 참고한 글 - 이서영님의 블로그

  • 참고한 글2 - 위키백과

  • BFS,DFS등이 한 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘인 반면, 플로이드-와샬 알고리즘은 그래프에서 모든 정점 사이의 최단거리를 구하는것이 가능하다.

  • 또한, 그래프의 간선중 음의 가중치가 존재해도 실행된다.

  • 단, 시간복잡도는 삼중반복문으로 인한 $O(V^3)$을 가지므로, 노드가 적을 경우에 활용해야 한다.

  • 또한, 간단한 수정을 통해 최단경로를 복원해낼수 있는 장점이 있다.

풀이

import sys

N, M = list(map(int, sys.stdin.readline().split()))

cost = [[N+1]*N for _ in range(N)]

for _ in range(0, M):
    a, b = list(map(int, sys.stdin.readline().split()))
    cost[a-1][b-1] = min(cost[a-1][b-1],1)
    cost[b-1][a-1] = min(cost[b-1][a-1],1)

cost_arr = []
for k in range(N):
    cost[k][k] = 0
    for i in range(N):
        for j in range(N):
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])


for k in range(N):
    cost_arr.append(sum(cost[k]))

print([cost_arr.index(x) for x in cost_arr if x == min(cost_arr)][0] + 1)

채점 결과

  • 정답

리뷰

  • 이번 코드는 대부분 이서영님의 블로그에서 나온 플로이드-와샬 코드를 기반으로 작성되었다.

  • 그래프의 최소 비용을 구하는 문제이므로 그래프의 초기값을 N+1로 초기화해주었다.

    • 그래프에서 나올수 있는 최대 비용은 N이기 때문이다.(간선 1당 비용1, 최대 N개의 간선)

  • 첫번째 반복문을 통해 점a에서 점b로 이어지는 간선을 가지는 그래프를 간단히 구현할수 있었다.

    • 초기값과 간선의 비용중 낮은값으로 변경하는 방식을 통해 각 간선의 비용을 입력해주었다.

    • 단, 이번 문제의 경우 간선의 비용은 무조건 1이므로, 전부 1로 통일된다.

    • 기존에 활용하던 dict를 통한 그래프는 아무래도 간선의 경로등을 추적하는데 지장이 있었는데, 이 방식으로 변경하니 상당히 수월했다.

  • k에서 k점으로 가는 비용(자기 자신에게 향하는 비용)은 0이므로 초기화해준다.

  • i에서 j로 바로 가는 cost와 i에서 임의의 지점을 거쳐 j로 가는 경우의 cost중 적은 경우, 즉 최단 경로의 비용을 저장해준다.

  • 케빈 베이컨 게임은 이 최단 비용의 합이 가장 작은 사람을 고르는 게임이므로, 비용함수의 각 줄을 더해 각 인원의 케빈 베이컨 수를 구한다.

  • 케빈 베이컨 수의 최솟값과 케빈베이컨수가 일치하는 사람들의 인덱스중 가장 작은값을 고르고, 사람 번호는 1부터 시작하므로 + 1 하여 리턴한다.

You May Also Enjoy