[백준-5567] 결혼식 / Python

5567번: 결혼식

import sys
from collections import deque

input = sys.stdin.readline

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


def search(start):
    visited = [0] * (n + 1)
    visited[start] = 1
    queue = deque()
    queue.append((start, 0))
    answer = 0
    while queue:
        x, cnt = queue.popleft()
        for i in graph[x]:
            if visited[i] == 0 and cnt < 2:
                visited[i] = 1
                queue.append((i, cnt + 1))
                answer += 1
    return answer


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

print(search(1))

 

해설

상근이의 학번이 1이기 때문에 search에 1을 넘겨줘 함수를 실행한다. deque에는 친구의 학번과 cnt를 넣어준다. 여기서 cnt는 관계를 의미한다. 예를 들어, cnt가 1이라면 직속 친구, cnt가 2라면 친구의 친구를 의미한다.

 

visited 방문처리와 친구 또는 친구의 친구라는 조건이 만족하면 deque에 학번과 cnt를 저장하고 answer를 하나씩 늘려준다.