백준 1389 - 파이썬

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

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

문제 풀이

이 문제는 문제에서 시키는데로만 하면 풀기 쉬운 문제이다. 구현 순서는 다음과 같다.

 

1. 양방향으로 각 노드들을 연결한다.

2. 1부터 n까지 완전 탐색하며 리스트의 합이 가장 작은 사람 출력한다(인덱스 출력하면 됨)

3. 합이 작은 사람이 여러명이면 가작 작은 수를 출력

 

BFS

import sys
from collections import deque
input = sys.stdin.readline

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

for _ in range(m):
  a,b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

def bfs(start):
  q = deque([start])
  visited = [-1] * (n + 1)
  visited[start] = 0
  
  while q:
    v = q.popleft()

    for i in graph[v]:
      if visited[i] == -1:
        q.append(i)
        visited[i] = visited[v] + 1

  return sum(visited)

result = []
for i in range(1,n+1):
  result.append(bfs(i))

print(result.index(min(result)) + 1)

여기서 주의할 점은 노드들을 연결할 때 반복문의 범위를 n이 아닌 m으로 해야 된다는 것이다. m개의 줄이 곧 간선의 개수인데 입력값이 둘다 5로 같다고 n을 입력하면 오답 처리를 받게 된다.(실제로 그랬음..)

 

또한 index() 함수로 값이 작은 인덱스를 출력해줬다.

 

플로이드 워셜

import sys
input = sys.stdin.readline

INF = 1e9

n,m = map(int, input().split())
graph = [[INF] * n for _ in range(n)]

for _ in range(n):
  a,b = map(int, input().split())
  graph[a-1][b-1] = 1
  graph[b-1][a-1] = 1

for k in range(n):
  for i in range(n):
    for j in range(n):
      if i == j: # 자기 자신과는 친구가 되지 못함
        graph[i][j] = 0
      else:
        graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])


print(graph)
bacon = []
for row in graph:
  bacon.append((sum(row)))

print(bacon.index(min(bacon)) + 1)

플로이드 워셜 풀이는 이 블로그를 참고했다. 또한 플로이드 워셜 알고리즘에 대한 자세한 내용은 여길 참고하면 된다.

 

느낀점

가장 합이 수의 인덱스를 출력하는것을 어떻게 할까 싶었는데 함수로 바로 구할 수 있어 좀 더 쉽게 푼거 같다. 파이썬의 장점이랄까..  또한 플로이드 워셜 알고리즘으로는 처음 풀어봤는데 최단경로를 계산할때 다익스트라 알고리즘과 함께 알아둬야 할 알고리즘인거 같다. BFS를 어느정도 풀고 나면 다익스트라와 플로이드워셜 알고리즘 문제도 많이 풀어봐야 되겠다.