[백준 1389번] 케빈 베이컨의 6단계 법칙

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

# 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결
# 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임

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

# 유저 중에서 케빈 베이컨의 수가 가장 작은 사람
# 즉, 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합
import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int,input().split())

graph = [set() for _ in range(n+1)]
minimum = float("inf")

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

def bfs(index):

    queue = deque([index])
    visited = [False]*(n+1)
    visited[index] = True

    dis = [0]*(n+1)

    while queue:
        
        node = queue.popleft()
        
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                dis[next_node] = dis[node]+1
                queue.append(next_node)

    return sum(dis)

for i in range(1,n+1):
    
    result = bfs(i)
    
    if result < minimum:
        minimum = result
        answer = i

print(answer)

 

이번 문제는 그래프로 연결된 친구 관계에서 각 유저마다 다른 유저들까지의 최단거리의 합이 최소값인 유저를 구하는 문제이다.

 

문제를 보자마자 다른 노드까지의 최단거리를 구하기 위해 BFS 알고리즘을 선택했고, 각 인덱스마다 BFS를 실행하여 최단거리들의 합을 구해주는 방식으로 풀이했다.

 

Chpt GPT의 뼈 때리는 조언

하지만 자꾸 메모리 초과가 발생하여 다른 풀이를 참고해보았는데, deque에 거리 정보(distance)를 함께 저장해주지 않고 1차원 배열을 별도로 선언하여 최단거리를 업데이트 시켜주는 방식으로 풀이하니 놀랍게도 메모리 초과가 해결되었다.(문제 자체가 메모리 제한이 빡빡했던 것 같다)

 

배운 점 및 느낀 점 📝

1. BFS 알고리즘을 사용할 때 queue에서 꺼낸 후에 방문 처리를 하게 되면 이전 노드에서 추가한 다른 노드가 방문 처리가 되지 않아 문제가 발생할 수 있다. 따라서 DFS 알고리즘을 사용할 때처럼 노드를 추가할 때 곧바로 방문처리 해주도록 하자.
2. deque에 담는 값이 복잡한 자료형일수록 대규모 입력에서 시간 초과나 메모리 초과가 발생할 확률이 높다. 따라서 메모리 초과가 발생한다면 알고리즘에서 사용한 자료구조를 단순화 해보도록 하자.