seukseok의 개인 블로그

BOJ 풀이 노트: DP와 BFS 기본기 점검

· tech

BOJ 1463, 2667을 통해 1차원 DP 최소 연산 문제와 격자 연결요소 탐색 기본기를 점검한 기록.

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

둘 다 자주 재등장하는 유형이라, 템플릿처럼 재사용 가능한 포인트 중심으로 정리한다.

1) BOJ 1463 - 1로 만들기

문제 핵심 요약

정수 N을 1로 만드는 최소 연산 횟수를 구하는 문제다. 가능한 연산은 다음 세 가지다.

핵심은 매 단계에서 선택지가 여러 개라서, 당장 좋아 보이는 선택만으로는 최적해를 보장하기 어렵다는 점이다.

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

이 문제는 최소 횟수를 묻고, i의 답이 i-1, i/2, i/3의 답과 직접 연결되므로 1차원 DP가 가장 자연스럽다.

정의:

점화:

작은 수부터 채우면 큰 수의 최적해를 안정적으로 만들 수 있다.

시간/공간 복잡도

실수하기 쉬운 포인트

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

dp[i] = dp[i - 1] + 1;
if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);

한 줄씩 후보를 좁혀가며 최소 연산을 보장하는 핵심 로직이다.

다른 풀이 가능성

BFS로 상태 그래프를 만들어도 최소 횟수를 구할 수 있다. 다만 이 문제는 상태 전이가 단순하고 범위가 연속적이라 DP가 구현량/가독성 측면에서 더 유리하다.

2) BOJ 2667 - 단지번호붙이기

문제 핵심 요약

N x N 지도에서 집(1)이 상하좌우로 연결된 묶음을 단지로 보고,

즉, 격자 그래프의 연결요소 개수와 각 컴포넌트 크기를 구하는 전형 문제다.

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

무가중치 격자에서 연결요소를 세는 문제이므로 BFS/DFS 둘 다 정석이다. 이번 풀이에서는 BFS를 사용했다.

절차:

  1. 격자를 순회하다가 방문하지 않은 1을 만나면 BFS 시작
  2. BFS가 확장한 칸 수를 해당 단지 크기로 기록
  3. 모든 단지 크기 수집 후 정렬

방문 처리는 별도 배열 대신 원본 격자에서 1 -> 0으로 바꿔 메모리를 줄였다.

시간/공간 복잡도

실수하기 쉬운 포인트

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

if (board[nx][ny] != '1') continue;
board[nx][ny] = '0';
q.push({nx, ny});
++cnt;

유효한 집 칸만 확장하고 즉시 방문 마킹해서 중복 방문을 막는다.

sort(sizes.begin(), sizes.end());

문제 요구사항(오름차순 출력)을 맞추는 마지막 단계다.

다른 풀이 가능성

재귀 DFS도 가능하다. 다만 입력 크기에 따라 재귀 깊이 이슈를 피하고 싶다면 큐 기반 BFS가 안전하다.

오늘 정리 포인트: