백준 5567번 - 결혼식

결혼식 문제 바로 가기

풀이 날짜: 2026-02-14

baekjoon 알고리즘 문제 풀이

풀이 코드


from collections import deque

n = int(input())
m = int(input())

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

dist = [-1] * (n+1)
dist[1] = 0

q = deque([1])

while q:
    current = q.popleft()
    if dist[current] == 2:
        continue

    for next in data[current]:
        if dist[next] == -1:
            dist[next] = dist[current] + 1
            q.append(next)

answer = sum(1 for i in range(1,n+1) if dist[i] in (1,2))
print(answer)

문제 접근

이 문제는 상근이(1번)가 결혼식에 초대할 사람의 수를 구하는 문제이다. 초대 조건은 다음과 같다.

1번의 직접 친구(거리 1)
친구의 친구(거리 2)

즉, 1번에서 시작해서 두 단계 이내에 도달 가능한 사람의 수를 구하는 문제이다. 자기 자신(1번)은 제외한다.

핵심 아이디어 - 그래프 구성

입력으로 친구 관계가 주어지므로, 이를 그래프로 표현해야 한다. 각 사람 번호를 인덱스로 하여, 친구 목록을 저장하는 인접 리스트를 사용했다.

data = [[] for _ in range(n+1)]
- data[i] = i번 사람의 친구 목록
- 양방향 관계이므로 서로 append한다.

BFS를 사용한 이유

이 문제의 핵심은 1번에서 시작했을 때 각 사람까지의 ‘거리’를 구하는 것이다. 친구는 거리가 1이고, 친구의 친구는 거리가 2이다. 이처럼 최단거리를 구해야 하므로 BFS가 적합했다.

거리 배열(dist)의 의미

-1: 아직 방문하지 않음
0: 시작점(1번)
1: 친구
2: 친구의 친구

즉, dist 배열은 방문 여부와 거리 정보를 동시에 저장한다.

정리

먼저 popleft()를 통해 현재 탐색할 노드를 꺼내고, 해당 노드의 거리가 이미 2라면 더 이상 그 노드를 탐색하지 않도록 continue로 확장을 중단해야 한다. 이후에 for문을 통해서 현재 노드와 연결된 모든 이웃을 확인하고, 아직 방문하지 않은 노드(dist[next] == -1)만 처리한다. 이때 방문 여부와 동시에 거리를 dist[current] + 1로 갱신한다. 그 후 다음 탐색 대상을 큐에 추가한다.

Vienna sausage