[Backjoon] 5567 결혼식 Python 문제 풀이

출처:5567번 결혼식

문제해석

• N=동기의 수
• 상근이는 1번이므로
  결과에서 포함되지 않음
• 친구와 친구의친구까지만 포함
• 1번 노드(상근이)를 시작으로 너비 우선 탐색(BFS)를 진행하면서 거리(dist)가 2 이하인 노드들의 개수만 세주면 된다.

해답코드

# 결혼식

import sys
from collections import defaultdict, deque

def bfs(start):
    ans=0
    isVisited = [0 for _ in range(n+1)]
    isVisited[start] = 1
    q = deque([[start,0]])
    while q:
        u, dist = q.popleft()
        if dist <= 2:
            ans += 1
        for v in graph[u]:
            if not isVisited[v]:
                isVisited[v] = 1
                q.append([v,dist+1])
    return ans-1

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
graph = defaultdict(list)
for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

print(bfs(1))