백준 5667 결혼식

약 15m

나의 답

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

n = int(input().rstrip())
m = int(input().rstrip())
graph = [[] for _ in range(n + 1)]
dist = [INF] * (n + 1)

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

def dijkstra(start):
    q = []
    heapq.heappush(q, (start, 0))
    dist[start] = 0
    while q:
        now, cost = heapq.heappop(q)
        if dist[now] < cost: continue
        for i in graph[now]:
            next = cost + i[1]
            if next < dist[i[0]]:
                dist[i[0]] = next
                heapq.heappush(q, (i[0], next))

dijkstra(1)

print(dist.count(1) + dist.count(2))

그래프로 그리고, 가중치가 1인 단순한 다익스트라 문제였다.
질문 게시판을 보니까 다들 bfs로 푸는 것 같았지만, 내가 보기엔 다익스트라가 더 효율적일것같았다!