BOJ 풀이 노트: LIS와 3차원 BFS 기본기 점검

2026. 2. 20. · tech

BOJ 11053, 7569를 문제 핵심 요약부터 접근 이유, 복잡도, 실수 포인트, 핵심 코드 설명까지 실전형으로 정리한 글.

오늘은 DP 1문제와 BFS 1문제를 묶어서 풀었다.

• BOJ 11053 - 가장 긴 증가하는 부분 수열
• BOJ 7569 - 토마토

둘 다 전형 문제지만, 구현에서 놓치기 쉬운 포인트가 명확해서 복습 효율이 좋다.

1) BOJ 11053 - 가장 긴 증가하는 부분 수열

문제 핵심 요약

수열이 주어졌을 때, 원소를 일부 골라 만든 증가 부분 수열의 최대 길이를 구하는 문제다. (부분 수열이므로 연속일 필요는 없다.)

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

이번에는 가장 직관적인 O(N^2) DP로 풀었다.

• dp[i]: i번째 원소를 마지막으로 하는 LIS 길이
• 초기값은 모두 1 (자기 자신만 고르는 경우)
• j < i에서 a[j] < a[i]이면 dp[i] = max(dp[i], dp[j] + 1)

N 범위에서 O(N^2)로 충분히 통과 가능하고, 디버깅이 쉬워 기본기 점검용으로 좋다.

시간/공간 복잡도

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

실수하기 쉬운 포인트

• 증가 조건을 a[j] <= a[i]로 쓰면 같은 수를 허용해서 오답이 난다. (<가 맞다)
• dp 초기값을 0으로 두면 단일 원소 케이스에서 길이가 깨진다.
• 정답은 dp 배열의 최댓값이지, 마지막 원소의 dp[N-1]이 아니다.

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

if (a[j] < a[i]) {
    dp[i] = max(dp[i], dp[j] + 1);
}

• i를 끝으로 하는 증가 부분 수열 길이를 갱신하는 핵심 전이식이다.

ans = max(ans, dp[i]);

• 매 인덱스마다 전체 최댓값을 유지해서 마지막에 바로 출력할 수 있다.

다른 풀이 가능성

이분 탐색 기반 LIS(O(N log N))로도 풀 수 있다. 문제 조건이 더 커지면 lower_bound를 이용한 방식이 필수에 가깝다. 다만 이번 범위에서는 O(N^2) DP가 이해와 구현 모두 안정적이다.

2) BOJ 7569 - 토마토

문제 핵심 요약

3차원 박스에서 익은 토마토(1), 안 익은 토마토(0), 빈 칸(-1)이 주어진다. 하루마다 익은 토마토의 상하좌우앞뒤 6방향으로 익음이 전파될 때, 모든 토마토가 익는 최소 일수를 구하는 문제다. 불가능하면 -1을 출력한다.

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

최소 일수 문제 + 동일 가중치 전파이므로 다중 시작점 BFS가 정석이다.

• 처음부터 익어 있는 모든 칸을 큐에 넣고 시작
• BFS로 인접한 안 익은 칸을 방문하면서 현재값 + 1로 날짜를 기록
• BFS 종료 후 0이 남아 있으면 실패(-1), 아니면 최댓값-1이 정답

3차원이라도 BFS 구조는 2차원과 동일하고, 방향 벡터만 6개로 늘어나면 된다.

시간/공간 복잡도

• 시간: O(H*N*M)
• 공간: O(H*N*M)

실수하기 쉬운 포인트

• 입력 순서가 M N H라는 점을 자주 헷갈린다.
• 방향 이동에서 층(h), 행(r), 열(c) 경계 체크를 섞어 쓰면 인덱스 버그가 난다.
• 정답 계산 시 날짜를 1부터 기록했기 때문에 최종 출력은 maxValue - 1이어야 한다.

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

if (box[nh][nr][nc] != 0) continue;
box[nh][nr][nc] = box[h][r][c] + 1;
q.push({nh, nr, nc});

• 아직 안 익은 토마토만 방문하고, 익은 날짜를 누적해서 기록한다.

if (box[h][r][c] == 0) {
    cout << -1 << '\n';
    return 0;
}

• BFS 후 미도달 칸(0) 존재 여부로 불가능 케이스를 즉시 판정한다.

다른 풀이 가능성

queue 대신 레벨 단위로 하루씩 카운트하는 BFS도 가능하다. 하지만 배열 자체에 날짜를 저장하는 방식이 별도 visited/day 배열이 필요 없어서 실전에서 더 간결하다.

오늘 정리 포인트:

• 11053은 DP 상태 정의(dp[i])를 정확히 잡는 연습에 좋다.
• 7569는 다중 시작점 BFS를 3차원으로 확장하는 전형 패턴이다.

기본기를 이런 식으로 묶어 훈련해두면, 응용 문제에서 설계 속도가 확실히 빨라진다.