99클럽 코테 스터디 2일차 TIL, BFS

• 문제: Baekjoon 1389: 케빈 베이컨의 6단계 법칙
  • 설명: 그래프가 주어질 때 모든 노드와의 최단 거리의 합이 가장 작은 노드의 번호를 출력하라
• 풀이
  • 모든 노드와의 최단 거리를 구해야하지만 가중치가 없기 때문에 BFS로 처음 도달하는 노드까지의 거리가 최단 거리이다.
  • 모든 노드들을 출발점으로 BFS를 1번씩 해주면서 각 노드와의 거리의 합을 구한다.
  • 이 합이 가장 작은 노드의 번호를 출력한다.
• 오늘의 회고
  • 처음에 거리의 합을 출력하는 줄 알고 답이 나오지 않아 10분 정도 헤맸던 것 같다.
  • 각 베이컨 수들을 모두 저장하고 이 수가 가장 작은 노드의 번호를 출력하여 해결했다.
    • 문제 잘 읽자!
  • 추가적으로 $N$을 $5,000$ 으로 잘못보고 플로이드-와샬은 생각도하지 않았는데 $N$이 $100$이라서 충분히 풀 수 있다.
    • 하지만 $N^3=10^6$ < $(N + E) \times N = 5.1 \times 10^5$이기 때문에 BFS가 이론상으로도 빠르긴 한데 의미없다! 둘 다 풀 수 있기 때문에!

Code

BFS

# Baekjoon01389.py
import sys
input = sys.stdin.readline

from collections import deque

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

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

    adj_list[a].append(b)
    adj_list[b].append(a)

bacon_number = [1_000_000_007 for _ in range(n + 1)]
for i in range(1, n + 1):
    curr_bacon = 0

    q = deque()
    visited = [False for _ in range(n + 1)]

    q.append((i, 0))
    visited[i] = True

    while (q):
        curr, dis = q.popleft()
        curr_bacon += dis

        for adj in adj_list[curr]:
            if (not visited[adj]):
                visited[adj] = True
                q.append((adj, dis + 1))

    bacon_number[i] = curr_bacon

ans = 0
for i in range(1, n + 1):
    if (bacon_number[ans] > bacon_number[i]):
        ans = i

print(ans)

Floyd-Warshall

# Baekjoon01389.py
import sys
input = sys.stdin.readline

INF = 1_000_000_007

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

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

    adj_mat[a][b] = 1
    adj_mat[b][a] = 1

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

ans = (0, INF)
for i in range(1, n + 1):
    curr = sum(adj_mat[i][1:]) # 노드의 번호가 1부터 시작이라 인덱스 맞추려고 0번째 값을 INF로 채웠으니 뺴줘야한다.
    if ans[1] > curr:
        ans = (i, curr)

print(ans[0])