BOJ 풀이 노트: 최단거리 BFS와 계단 DP 기본기 점검

2026. 2. 24. · tech

BOJ 14940, 2579를 BFS 거리 전파와 점화식 설계 관점에서 실전적으로 정리한 풀이 노트.

오늘은 그래프 탐색 1문제 + DP 1문제로 루틴을 구성했다.

• BOJ 14940 - 쉬운 최단거리
• BOJ 2579 - 계단 오르기

두 문제 모두 구현 자체는 짧지만, 출력 규칙과 점화식 조건을 정확히 잡아야 한 번에 통과된다.

1) BOJ 14940 - 쉬운 최단거리

문제 핵심 요약

지도에서 목표 지점(값 2)으로부터 각 칸까지의 최단거리를 구해 출력하는 문제다.

• 이동 가능한 칸(값 1): 도달 가능하면 거리, 도달 불가능하면 -1
• 이동 불가능한 칸(값 0): 항상 0 출력

핵심은 목표 지점 하나에서 시작해 전체로 퍼지는 최단거리를 구하는 형태라는 점이다.

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

무가중치 격자 최단거리는 BFS가 정석이다. 이 문제는 모든 칸에서 목표를 향해 역탐색하는 대신, 목표 지점에서 시작해 BFS 한 번으로 전체 거리를 채우는 편이 훨씬 단순하다.

구현 포인트:

1. 입력을 받으면서 목표 지점(2)을 큐에 넣고 거리 0 설정
2. 값이 0인 칸은 애초에 답이 0이므로 거리 배열도 0으로 고정
3. BFS로 값이 1인 칸만 확장하면서 거리 갱신
4. 끝까지 방문되지 않은 값 1 칸은 -1 유지

시간/공간 복잡도

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

실수하기 쉬운 포인트

• 0인 칸을 -1로 남겨두면 오답이 된다(이 문제에서 0 칸 출력은 항상 0).
• 시작점(2) 거리 초기화를 빼먹으면 전체가 -1로 남는다.
• 인접 칸 확장에서 경계 체크 순서를 잘못 두면 런타임 에러가 발생한다.

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

if (grid[i][j] == 0) {
    dist[i][j] = 0;
}

문제의 출력 규칙을 그대로 선반영해서 오답 가능성을 줄인다.

if (grid[nx][ny] == 0) continue;
if (dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[x][y] + 1;

갈 수 없는 칸을 제외하고, 아직 방문하지 않은 칸에만 최단거리 레벨을 전파하는 BFS 핵심 부분이다.

다른 풀이 가능성

가중치가 없는 문제라 다익스트라까지는 과하다. 멀티 소스 BFS 구조로 일반화할 수는 있지만, 이 문제는 시작점이 하나라 단일 BFS가 가장 직관적이다.

2) BOJ 2579 - 계단 오르기

문제 핵심 요약

각 계단 점수가 주어질 때, 마지막 계단은 반드시 밟으면서 점수 합 최댓값을 구하는 문제다. 단, 연속된 세 계단을 모두 밟을 수 없다는 제약이 핵심이다.

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

탐욕으로는 연속 3계단 금지 제약을 전역적으로 보장하기 어렵다. 그래서 dp[i] = i번째 계단까지의 최대 점수로 두고, i번째에 도착하는 경우를 둘로 나눈다.

• i-2 -> i로 오는 경우
• i-3 -> i-1 -> i로 오는 경우 (i-2를 건너뛰어 연속 3계단 방지)

점화식: dp[i] = max(dp[i-2], dp[i-3] + score[i-1]) + score[i]

이 식 하나로 제약을 자연스럽게 만족시킬 수 있다.

시간/공간 복잡도

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

실수하기 쉬운 포인트

• n=1, n=2 초기값 처리를 누락하면 인덱스 오류/오답이 난다.
• dp[i-1] + score[i] 형태를 섞어 쓰면 연속 3계단 위반 케이스가 들어오기 쉽다.
• 마지막 계단 필수 조건을 놓치고 중간 최대값만 구하면 문제 요구를 어기게 된다.

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

dp[2] = score[1] + score[2];

초기조건을 분명히 두면 이후 점화식이 깨끗하게 이어진다.

dp[i] = max(dp[i - 2], dp[i - 3] + score[i - 1]) + score[i];

연속 3계단 금지 조건을 구조적으로 반영한 핵심 점화식이다.

다른 풀이 가능성

(현재 위치, 연속으로 밟은 수)를 상태로 둔 2차원 DP로도 풀 수 있다. 다만 이 문제는 1차원 점화식이 더 짧고 실전에서 구현 실수가 적다.

오늘 정리 포인트:

• 14940은 출력 규칙(0/1/2 처리)을 먼저 고정하고 BFS를 태우면 깔끔하게 끝난다.
• 2579는 도착 직전 패턴을 두 가지로 분기하는 점화식을 확실히 기억하면 유사 계단 DP에 재사용하기 좋다.

루틴 문제라도 이런 식으로 정리해두면, 다음에 비슷한 유형을 볼 때 풀이 재현 속도가 빨라진다.