[백준] 1389 케빈 베이컨의 6단계 법칙 (python 파이썬)

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

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

문제를 보다가 최근에 공부한 플로이드 워샬로 풀 수 있을 거 같아 사용했더니 통과됐다.

 

풀이 과정

for _ in range(M):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            graph[i][j] = 0

플로이드 방식으로 풀때 생각한 건 그래프 생성과 가중치다.

그래프의 간선 양방향으로 하고 가중치는 1로 설정했다.

 

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

k: 중간 경유 노드, i: 시작 노드, j: 도착 노드

플로이드 알고리즘 부분이다. 시간 복잡도 O(V^3)으로 최대 100*3 = 10^6이다.

 

bacon = INF
answer = 0
for i in range(N, 0, -1):
    s = sum(graph[i][1:])
    if bacon >= s:
        bacon = s
        answer = i
print(answer)

문제에서 베이컨 수가 가장 적은 사람이라 했으니 n번째 행의 합이 제일 적은 사람을 찾으면 된다.

근데 베이컨 수가 가장 적은 사람이 여러 명이면 번호가 가장 작은 사람을 출력하라 했으므로

for문을 역순으로 실행하면 된다.

 

 

전체 코드

import sys
INF = int(1e9)
N, M = map(int,input().split())
graph =[[INF] * (N + 1)  for _ in range(N + 1)]

for _ in range(M):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            graph[i][j] = 0

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

bacon = INF
answer = 0
for i in range(N, 0, -1):
    s = sum(graph[i][1:])
    if bacon >= s:
        bacon = s
        answer = i
print(answer)