[python] 백준 5567 결혼식

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

5567번: 결혼식

 

문제 해결

• 그래프의 전형적인 문제
• 처음 시작 노드 1에서 한 번 다른 노드로 이동할 때마다 횟수 변수 cnt를 1씩 증가시킬 때 cnt가 2 이하인 노드들의 개수를 구하는 문제
• que를 만든 후 연결 된 노드로 이동하면서 cnt가 2이상이면 더 뻗어 나갈 수 없으므로 멈추고 이동한 노드의 cnt가 2보다 작으면 que에 넣어 다른 노드로 또 이동한다.

 

CODE

from collections import deque

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

que = deque()
que.append((1,0))
visited = [0 for _ in range(n+1)]
visited[1] = 1
answer = 0
while que:
    x, cnt = que.popleft()
    if cnt >=2:continue
    for friend in graph[x]:
        if visited[friend]==0:
            visited[friend] = 1
            que.append((friend,cnt+1))
            answer += 1
print(answer)