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

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

 

최단경로 문제다.

 

그래프가 주어지고 한 점에서 다른 모든 점들까지의 거리가 최소인 점을 찾는 문제다.

입력은 연결된 점들의 리스트가 들어온다.

 

가장 먼저 생각 난 방법은 플로이드 워셜이다.

생각은 났는데 공부한 지 좀 지난 개념이라 알고리즘 흐름을 다시 찾아봤다.

간단하게 설명하자면, 모든 지점에서 다른 점들까지의 최단 경로를 한 번에 구하는 방법이다.

2차원 배열을 이용하고 배열의 각 칸은 i부터 j까지의 최단 거리를 의미한다.

3중 반복문(k, i, j)을 통해 min(arr[i][j], arr[i][k] + arr[k][j])를 수행한다.

위의 점화식이 의미하는 바는 i부터 j까지 가는 경로 중 k를 거쳐가는 경우의 수를 고려하는 것이다.

 

플로이드 워셜 알고리즘만 이해하면 코드를 짜는 데는 문제가 없다.

주의해야 할 점은 최솟값을 10000 이상으로 설정해야 한다.

사람이 최대 100명이라고 해서 처음에는 100으로 설정하는 실수를 범했다...

 

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
arr = [[10001 for _ in range(n + 1)] for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    arr[a][b] = 1
    arr[b][a] = 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k])

res = 0
tmp = 10001
for i in range(1, n + 1):
    sum = 0
    for j in range(1, n + 1):
        if i == j: continue
        sum += arr[i][j]
    if tmp > sum:
        tmp = sum
        res = i

print(res)

 

---

 

추가적으로 플로이드 워셜은 노드 간의 가중치가 있을 때 사용할 수 있는 방법인데

이 문제에는 가중치가 없기 때문에 bfs를 사용할 수 있을 것 같다고 생각했다.

 

기본적인 bfs와 동일하기 때문에 설명은 생략...!

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
arr = [[] for _ in range(n + 1)]
res = []

for i in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
    
for i in range(1, n + 1):
    visit = [0 for _ in range(n + 1)]
    q = [[i, 1]]
    visit[i] = 1
    cnt = 0
    while len(q) != 0:
        tmp = q.pop(0)
        for j in range(len(arr[tmp[0]])):
            k = arr[tmp[0]][j]
            if visit[k] == 1: continue
            visit[k] = 1
            q.append([k, tmp[1] + 1])
            cnt += tmp[1]

    res.append(cnt)
    
print(res.index(min(res)) + 1)

 

여러가지 방법으로 해결했을 때의 뿌듯함 >.0