[백준] 5567 결혼식 / BFS / Python 실2

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

 

BFS를 이용해 탐색하는데, depth 제한이 있음에 주의해야 한다

 

일단 상근이 학번인 1부터 시작한다

 

q를 돌면서

현재 탐색 중인 요소 번째에 친구 관계를 분석한다

만약 탐색한 적이 없는 친구면, visited로 바꿔주고,

초대할 친구 목록에 추가해준다

초대할 친구 목록은 set으로 선언했기 때문에 중복되지 않는 요소만 추가된다

 

추가 탐색은 친구의 친구까지만 가능하기 때문에

현재 탐색 요소가 상근를 기준으로 친구를 탐색할 때만 q에 추가한다

 

그 외에 q에 추가할 경우, 친구의 친구의 친구를 탐색할 수 있기 때문

 

탐색을 모두 마친 후 invite의 길이를 출력하면 된다

 

from collections import deque
n = int(input())
m = int(input())
f = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int, input().split())
    f[a].append(b)
    f[b].append(a)
    
visited=[False]*(n+1)
invite=set()

q = deque([1])
visited[1] = True

while q:
    cur = q.popleft()
    for friend in f[cur]:
        if not visited[friend]:
            visited[friend]=True
            invite.add(friend)
            if cur==1:
                q.append(friend)
print(len(invite))