[알고리즘] BOJ 1389번 - 케빈 베이컨의 6단계 법칙(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

4 / 50

 

탐색

4 / 50(NEW!)

 

기초 동적 프로그래밍

4 / 50

 

투포인터

0 / 10

---

문제

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

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

→ solved.ac 기준 실버 1

→ class 3

 

---

문제 해결 아이디어

각 사람은 연결 되어있으며 케빈 베이컨의 수는 최단 경로 == 그래프 문제

→ 모든 노드에 대해서 노드 n이 각 노드로 갈 때 최소 경로의 합을 구해야 함.

→ 모든 노드에 대한 최소 경로는 플로이드 위셜 알고리즘(모든 노드에서 다른 모든 노드까지의 최단 경로 모두 계산) 활용

: 실제로 N의 최댓값이 100이므로 O(N^3)을 가진 플로이드 위셜 알고리즘 사용 가능

→ 최단 경로의 합을 구해서 가장 작은 합을 가진 노드의 인덱스를 출력하면 끝

---

구현

내 풀이(플로이드 위셜 알고리즘)

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

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

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

# a와 b가 같은 사람인 경우 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 점화식에 따라 플로이드 위셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

value = INF
answer = 0
for a in range(1, n + 1):
    if value > sum(graph[a][1:]):
        value = sum(graph[a][1:])
        answer = a

print(answer)

 

다른 사람 풀이(BFS 활용)

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

def bfs(graph, start, visited):
	# 최단 경로를 저장하는 리스트 초기화
    distance = [0] * (n + 1)
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소를 뽑기
        v = q.popleft()
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                distance[i] = distance[v] + 1
                queue.append(i)
                visited[i] = True
    return sum(distance)

# 입력받아서 그래프 초기화
n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

# 최단 경로 담는 리스트
result = []
for i in range(1, n+1):
    visited = [False] * (n + 1)
    result.append(bfs(graph, i))
# 가장 짧은 경로를 가진 원소의 인덱스 + 1 출력
print(result.index(min(result)) + 1)

---

메모

• 걸린 시간: 40분
  • 아이디어 구상하고 구현하는데 10분 정도, 그 밖에 코드 문제 찾는데 30분 소요..
  • 이 부분만 고치니까 바로 됐음

value = sum(graph[a][1:])
answer = 1
for a in range(2, n + 1):
    if value > sum(graph[a][1:]):
        value = sum(graph[a][1:])
        answer = a

• 아니 왜 안 됐지 하고 다시 보니까 value = sum(graph[1][1:])이라고 해놨었다...허허허허허헣ㅎ

---

마치며

아직은 반례 찾거나 코드 문제점 찾는데 시간 많이 소요하는 듯

그래도 문제 아이디어 파악하는 속도는 조금씩 늘고 있어서 좋아용