BOJ 풀이 노트: DP와 그래프 도달성 기본기 점검

2026. 3. 1. · tech

BOJ 1932와 11403을 대상으로, 삼각형 DP와 경로 존재 행렬 갱신(Floyd-Warshall)을 구현 실수 포인트 중심으로 정리한 풀이 노트.

오늘은 서로 결이 다른 2문제를 묶어서 풀었다.

• BOJ 1932 - 정수 삼각형
• BOJ 11403 - 경로 찾기

1932는 전형적인 누적 최적화 DP, 11403은 정점 간 도달 가능성을 행렬로 갱신하는 그래프 문제다. 둘 다 구현은 짧지만, 인덱스 처리나 갱신 순서를 잘못 잡으면 틀리기 쉬운 유형이다.

1) BOJ 1932 - 정수 삼각형

문제 핵심 요약

삼각형 형태로 주어진 수들에서, 맨 위에서 시작해 바로 아래층의 인접한 칸으로만 내려가며 얻을 수 있는 최대 합을 구하는 문제다.

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

각 칸 (i, j)에 도달하는 최대 합은 바로 윗줄의 두 후보 중 큰 값에서 내려오는 방식으로 결정된다.

• 왼쪽 끝(j=1)은 위의 j=1에서만 올 수 있음
• 오른쪽 끝(j=i)은 위의 j-1에서만 올 수 있음
• 내부는 max(dp[i-1][j-1], dp[i-1][j])

즉, 부분 문제 최적값을 누적하면 전체 최적해가 되는 전형적인 bottom-up DP다.

시간/공간 복잡도

• 시간: O(n^2)
• 공간: O(n^2)

실수하기 쉬운 포인트

• 삼각형 경계(왼쪽/오른쪽 끝) 처리를 일반식으로 밀어붙이다가 인덱스 범위를 벗어나기 쉽다.
• dp 초기값을 0으로 둘 때, 문제 조건(자연수) 기반으로 안전한지 확인해야 한다.
• 입력을 1-index로 받을지 0-index로 받을지 처음에 통일하지 않으면 디버깅 시간이 길어진다.

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

if (j == 1) {
    dp[i][j] = dp[i - 1][j] + triangle[i][j];
} else if (j == i) {
    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
} else {
    dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
}

경계와 내부를 분리해 전이식을 명확히 처리했다. 이 분기만 정확하면 구현 난이도는 크게 떨어진다.

for (int j = 1; j <= n; ++j) {
    answer = max(answer, dp[n][j]);
}

마지막 줄 어느 칸에서 끝나도 되므로, 마지막 행의 최대값을 최종 답으로 취한다.

다른 풀이 가능성

• dp를 1차원 배열로 압축해 O(n) 공간으로 줄일 수 있다(오른쪽에서 왼쪽으로 갱신 필요).
• 재귀 + 메모이제이션(top-down)으로도 같은 점화식을 구현할 수 있다.

2) BOJ 11403 - 경로 찾기

문제 핵심 요약

주어진 방향 그래프에서 모든 정점 쌍 (i, j)에 대해, i에서 j로 가는 경로가 존재하는지(1/0) 출력하는 문제다.

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

도달 가능 행렬 reachable[i][j]를 두고, 중간 정점 k를 허용하면서 갱신한다.

i -> k와 k -> j가 가능하면 i -> j도 가능하므로, reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j])

이는 Floyd-Warshall의 최단거리 버전이 아니라, 도달성(Transitive Closure) 버전이다. 정점 수가 작아(N <= 100) O(N^3)이 충분히 통과된다.

시간/공간 복잡도

• 시간: O(N^3)
• 공간: O(N^2)

실수하기 쉬운 포인트

• 자기 자신으로 가는 경로(i -> i)도 사이클이 있으면 1이 될 수 있다는 점을 놓치기 쉽다.
• 입력 그래프가 방향 그래프인데 무심코 양방향처럼 다루면 오답이 된다.
• k를 가장 바깥 루프로 두는 갱신 순서를 바꾸면 논리가 깨질 수 있다.

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

for (int k = 0; k < N; ++k) {
    for (int i = 0; i < N; ++i) {
        if (!reachable[i][k]) continue;
        for (int j = 0; j < N; ++j) {
            if (reachable[k][j]) {
                reachable[i][j] = 1;
            }
        }
    }
}

i -> k가 불가능한 경우를 미리 건너뛰어 불필요한 내부 연산을 줄였다. 핵심은 k를 경유지로 쓰는 삼중 루프 구조다.

다른 풀이 가능성

• 각 정점에서 BFS/DFS를 한 번씩 수행해도 O(N*(N+M))으로 해결 가능하다.
• 인접 행렬 기반 비트셋 최적화(C++ bitset)를 쓰면 상수 시간 면에서 더 빠르게 구현할 수 있다.

오늘 정리 포인트는 두 가지다.

• 1932: 경계 분기만 정확히 처리하면 안정적인 DP 문제다.
• 11403: Floyd-Warshall을 거리 대신 도달성으로 바꿔 생각하면 바로 풀린다.

이런 기본 패턴을 매일 2문제씩 반복하면, 문제를 처음 봤을 때 “이건 어느 전형으로 떨어지는지”를 빠르게 판단하는 힘이 확실히 좋아진다.