BOJ 풀이 노트: 연결 요소 탐색과 1,2,3 더하기 DP 점검

2026. 2. 28. · boj-note

오늘은 그래프와 DP 기본기를 같이 점검하는 조합으로 2문제를 풀었다.

• BOJ 11724 - 연결 요소의 개수
• BOJ 9095 - 1, 2, 3 더하기

11724는 “방문 처리 누락 없이 컴포넌트 수 세기”가 핵심이고, 9095는 “작은 점화식을 정확히 세우고 재사용하기”가 핵심이다. 둘 다 난도 대비 자주 쓰이는 기본 패턴이라 꾸준히 반복할 가치가 있다.

1) BOJ 11724 - 연결 요소의 개수

문제 핵심 요약

무방향 그래프에서 서로 도달 가능한 정점 묶음(연결 요소)이 몇 개인지 구하는 문제다.

접근 아이디어(왜 이 방법인지)

정점 1부터 N까지 순회하면서, 아직 방문하지 않은 정점을 시작점으로 BFS를 한 번 돌리면 그 BFS가 정확히 연결 요소 하나를 덮는다.

즉, “미방문 정점을 하나 잡아 탐색 시작”할 때마다 연결 요소 카운트를 1 증가시키면 된다. DFS로 풀어도 동일하지만, 이번 풀이에서는 큐 기반 BFS로 구현했다.

시간/공간 복잡도

• 시간: O(N + M)
• 공간: O(N + M) (인접 리스트 + 방문 배열 + BFS 큐)

실수하기 쉬운 포인트

• 정점 번호가 1부터 시작하므로 배열 크기를 N+1로 잡아야 안전하다.
• 무방향 그래프이므로 간선을 양방향으로 모두 넣어야 한다.
• 간선이 전혀 없는 고립 정점도 각각 연결 요소 1개로 세야 한다.

C++ 코드 설명(핵심 라인)

for (int start = 1; start <= N; ++start) {
    if (visited[start]) continue;
    components++;
    ...
}

미방문 정점을 만날 때마다 새 BFS를 시작하고, 그 시점에 연결 요소 수를 증가시킨다.

for (int nxt : graph[cur]) {
    if (visited[nxt]) continue;
    visited[nxt] = true;
    q.push(nxt);
}

인접 정점을 큐에 넣기 전에 바로 방문 체크를 해 중복 삽입을 막는다.

다른 풀이 가능성

• 재귀 DFS로도 같은 복잡도로 해결 가능하다.
• Union-Find(Disjoint Set)로 간선을 합치고 최종 부모 개수를 세는 방식도 가능하다.

2) BOJ 9095 - 1, 2, 3 더하기

문제 핵심 요약

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구한다. 순서가 다르면 다른 경우로 센다.

접근 아이디어(왜 이 방법인지)

마지막에 더한 수를 기준으로 보면 점화식이 바로 나온다.

• 마지막이 1이면 n-1을 만드는 경우
• 마지막이 2면 n-2
• 마지막이 3이면 n-3

그래서 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 가 된다. 문제 입력 범위가 작아서(최대 10) 미리 dp[10]까지 채워 두고 각 테스트케이스를 즉시 출력하면 된다.

시간/공간 복잡도

• 전처리: O(10)
• 질의당 출력: O(1)
• 공간: O(10)

실수하기 쉬운 포인트

• 기저값 dp[1]=1, dp[2]=2, dp[3]=4를 틀리면 전체가 다 틀어진다.
• “순서가 다르면 다른 경우”라는 조건을 놓치면 조합 문제로 오해하기 쉽다.

C++ 코드 설명(핵심 라인)

dp[1] = 1;
dp[2] = 2;
dp[3] = 4;

점화식 전개를 위한 필수 초기값이다.

for (int i = 4; i <= 10; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}

작은 값부터 차례대로 채우는 전형적인 bottom-up DP다.

다른 풀이 가능성

• 메모이제이션 재귀(top-down)로도 구현 가능하다.
• 생성함수 관점으로 해석할 수도 있지만, 이 문제는 단순 DP가 가장 빠르고 명확하다.

오늘 정리 포인트는 간단하다.

• 11724는 “미방문 시작점마다 탐색 1회”라는 연결 요소 카운팅 패턴을 확실히 익히는 문제.
• 9095는 “마지막 선택 기준 점화식”으로 DP 사고를 익히기 좋은 문제.

기본기 문제라도 매일 2문제씩 꾸준히 쌓으면, 이후 골드 구간 문제에서 구현 실수가 확실히 줄어든다.