[BOJ/python] 5567: 결혼식

문제

✔️ silver 2
그래프 이론
그래프 탐색

문제 흐름

1. friends 딕셔너리에 입력받은 친구 관계를 넣어준다.
2. 상근이인 1을 시작으로 bfs 방식으로 깊이 2까지만 탐색하도록 했다.

여기서 초대하는 친구들을 집합attend를 통해 체크해서 중복 체크는 따로 하지 않았다.
하지만 이때문에 상근이가 여기 다시 포함될 수 있으므로 전체 집합 길이에서 -1을 해줘야 한다.
상근이가 친구가 없는 경우도 있으므로 -1을 했을 때 0보다 작은 경우는 0을 출력하도록 했다.

코드

# 결혼식
# graph

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

if __name__ == "__main__":
    n = int(input())
    m = int(input())
    friends = {i:[] for i in range(1, n+1)}
    for i in range(m):
        a, b = map(int, input().split())
        friends[a].append(b)
        friends[b].append(a)
    
    q = deque([(1, 0)])
    attend = set()
    while q:
        x, i = q.popleft()
        if i >= 2:
            continue
        for nx in friends[x]:
            q.append((nx, i+1))
            attend.add(nx)
    
    answer = len(attend)-1 if len(attend)-1 > 0 else 0
    print(answer)

마무리

원래는 강의 먼저 듣고 문제를 풀었어야 했는데 어쩌다 보니 문제 먼제 풀게 됐다.
그래프쪽은 내가 관심있게 듣기 좋은 알고리즘 파트라서 살짝 기대가 된다!