[백준] 5567 - 결혼식

문제 링크 : https://www.acmicpc.net/problem/5567

문제 탐색하기

1) 문제 분석

동기의 수 n (2 ≤ n ≤ 500)
친구 관계의 개수 m (1 ≤ m ≤ 10 000)
이후 m개 줄에 걸쳐 a, b가 친구라는 관계 (양방향)
상근이의 학번은 1번
초대 대상: 상근이의 직접 친구(1촌)와 친구의 친구(2촌)
출력: 초대할 동기의 수

2) 가능한 시간복잡도

(1) 입력 처리

노드 수: n (최대 500)
간선 수: m (최대 10,000)
친구 관계 입력: O(m)→ 총 입력 처리 시간: O(m)

(2) 그래프 구성

인접 리스트 방식: 친구 관계를 양방향으로 연결→ O(m)

(3) BFS 탐색

최악의 경우 모든 노드를 방문
하지만 실제 탐색은 2단계 이내에서 멈춤→ 시간복잡도는 O(n)(단, 문제 조건 상 2촌까지 탐색만 수행되므로 현실적으로 매우 빠름)

(4) 전체 시간복잡도

입력: O(m)
그래프 구성: O(m)
탐색: O(n)→ 총합: O(m + n)

3) 알고리즘 선택 이유

이 문제는 시작 노드(상근이)에서 최대 2단계 거리까지 탐색하는 문제로, 그래프 탐색 알고리즘인 BFS를 사용하면 효율적이다.

BFS는 레벨(거리 개념)을 기준으로 탐색을 확장하기 때문에, 1촌, 2촌 개념을 명확히 구현할 수 있다.

직접 친구: 상근이와 연결된 노드 (depth 1)
친구의 친구: 상근이와 거리 2인 노드 (depth 2)

방문한 노드를 체크하여 중복 초대를 막고, depth를 기준으로 초대 범위를 제한하면 된다.

→ 그래프 레벨 탐색이 가능한 BFS가 가장 직관적이며 안정적인 해법이다.

코드 설계하기

1. 실행 구조

1) 입력 처리

첫 줄: 동기의 수 n
둘째 줄: 친구 관계 수 m
이후 m개의 줄에 친구 관계 a b가 주어진다.

2) 그래프 구성

인접 리스트 형태로 그래프를 구성한다.
친구 관계는 양방향이므로, a ↔ b 양쪽 모두 연결한다.

3) BFS 탐색

시작 노드: 상근이(1번)
visited 배열을 통해 방문 여부를 체크
depth를 함께 관리하여, 2촌까지만 초대 가능하도록 제한

4) 초대 인원 수 계산

상근이를 제외한 2촌 이내 모든 방문 노드를 count
최종적으로 초대한 인원 수를 출력

2. 고민이 되었던 부분

1) "탐색 깊이 제한" 구현

단순 BFS를 사용하면 모든 노드를 순회하게 되므로, 친구의 친구까지만 탐색하는 제약을 어떻게 줄 것인지가 핵심이었다.
→ queue에 함께 depth 값을 넣어서 거리 제한을 설정했다.

2) "중복 초대 방지"

한 사람이 여러 경로로 도달할 수 있기 때문에, 이미 초대한 사람을 다시 초대하지 않도록 visited 배열을 사용하여 중복을 방지하였다.

정답 코드

JavaScript

// 사용 언어 : Javascript

// 파일 시스템 모듈 불러오기
const fs = require('fs');

// 입력값을 한 줄씩 배열로 저장
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const n = Number(input[0]); // 동기 수
const m = Number(input[1]); // 친구 관계 수

// 친구 관계 배열 만들기
const relations = input.slice(2).map((line) => line.split(" ").map(Number));

// 인접 리스트 생성
const graph = Array.from({ length: n + 1 }, () => []);
for (const [a, b] of relations) {
    graph[a].push(b);
    graph[b].push(a); // 양방향 관계
}

// 방문 여부 체크
const visited = Array(n + 1).fill(false);

// BFS 탐색 시작
let inviteCount = 0;
const queue = [];
visited[1] = true; // 상근이 방문 처리
// 친구 추가
for (const friend of graph[1]) {
    if (!visited[friend]) {
        visited[friend] = true;
        queue.push(friend);
        inviteCount++; // 친구는 바로 초대
    }
}

// 친구의 친구 탐색
while (queue.length > 0) {
    const current = queue.shift();
    for (const friend of graph[current]) {
        if (!visited[friend]) {
            visited[friend] = true;
            inviteCount++; // 친구의 친구 초대
        }
    }
}

console.log(inviteCount);

마무리하며

이번 문제는 단순한 그래프 탐색 문제처럼 보이지만, "탐색 깊이 제약"이라는 조건을 정확하게 구현하는 것이 핵심이었다. 특히 BFS에서 거리 개념을 함께 추적해야 하며, 단순히 모든 노드를 방문하는 것이 아니라 2촌까지의 유효한 초대 대상만 정확히 계산해야 한다는 점에서,
단순한 구현 이상의 사고가 필요했다.

또한, BFS에서 visited와 depth를 동시에 고려하는 방식은 그래프 탐색 문제에서 자주 활용되는 패턴이므로, 유사한 문제에서 계속 적용될 수 있는 중요한 포인트였다. 결국 이 문제를 풀면서 "문제 조건을 정확히 구현하는 힘"이 얼마나 중요한지를 다시금 느꼈고, 앞으로도 조건에 따른 제약 처리와 로직 분리를 꼼꼼하게 구현하는 습관을 유지하고 싶다는 생각을 하게 되었다.

최근 글