[백준] 5567(파이썬) - 결혼식

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

5567번: 결혼식

• 이 문제를 처음 읽고 든 생각은 '어쨌든 그래프니까 bfs를 이용해야겠다'였습니다.
• bfs로 풀다 보니 생각보다 로직이 간단했습니다.
• bfs로직을 풀 때, 부모 노드에서 자식 노드로 갈 때 visited [부모 노드]에서 +1을 해서 visited [자식 노드] 값으로 넣어줬습니다.
• 그러면 visited에 담기는 값이 1번부터 시작해서 몇 번을 거친 친구인지가 나오게 되는데, 조건에서 친구의 친구까지만 초대를 한다고 했으니까 visited 가 4보다 작을 경우만 result += 1을 해줘서 정답을 구했습니다.

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

n = int(input())
m = int(input())
graph = [ [0] * (n+1) for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

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

def bfs(x):
    q = deque()
    visited[x] = 1
    q.append(x)
    while q:
        a = q.popleft()
        for i in graph[a]:
            if visited[i] == 0:
                q.append(i)
                visited[i] = visited[a] + 1

bfs(1)
result = 0
for i in range(2,n+1):
    # 본인이거나 친구거나, 친구의 친구거나 경우의 수가 최대 3개
    if visited[i] < 4 and visited[i] != 0:
        result += 1
print(result)