BOJ 풀이 노트: DSLR 상태 탐색과 그림 BFS 기본기 점검

2026. 3. 22. · tech

오늘은 BOJ 9019와 1926을 묶어 상태 전이 최단 경로 BFS와 격자 연결요소 BFS를 실수 방지 관점으로 정리했다.

오늘은 BFS를 서로 다른 형태로 쓰는 2문제를 선택했다.

• BOJ 9019 - DSLR
• BOJ 1926 - 그림

둘 다 BFS지만, 9019는 숫자 상태 전이를 다루는 문제이고 1926은 2차원 격자에서 연결된 영역을 세는 문제다. 구현 디테일이 달라서 같이 복습하기 좋았다.

1) BOJ 9019 - DSLR

문제 핵심 요약

정수 A를 B로 바꾸는 최소 연산 수열을 구한다. 가능한 연산은 D, S, L, R 네 가지이며, 정수 범위는 0~9999로 고정이다. 정답은 최소 길이의 연산 문자열이다.

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

각 숫자(0~9999)를 그래프의 정점으로 보고, 연산 4개를 간선으로 보면 된다. 모든 간선 비용이 1이므로 BFS를 쓰면 최초 도달이 최단 경로다.

핵심은 경로 복원이다.

• prev[next] = cur로 이전 정점을 저장
• op[next] = 사용한 연산 저장
• 목표 B에서 A까지 역추적 후 뒤집기

이렇게 하면 최소 연산 문자열을 정확히 복원할 수 있다.

시간/공간 복잡도

• 시간: O(10000) (각 상태를 최대 1번 방문, 상태당 연산 4개)
• 공간: O(10000) (방문/이전 정점/연산 기록)

실수하기 쉬운 포인트

• L, R 회전 식을 잘못 써서 숫자 자릿수 이동이 틀리는 경우
• 방문 체크를 늦게 해서 같은 정점이 큐에 여러 번 들어가는 경우
• 목표 도달 후 경로 복원 시 역순 처리(reverse)를 빼먹는 경우

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

int l = (cur % 1000) * 10 + (cur / 1000);
int r = (cur / 10) + (cur % 10) * 1000;

네 자리 정수 회전을 산술로 처리한 부분이다. 문자열 변환 없이 상수 시간으로 다음 상태를 만든다.

prev[nx] = cur;
op[nx] = c;

최단 경로 복원을 위해 다음 상태의 직전 정점과 연산 문자를 저장한다.

다른 풀이 가능성

• unordered_map 기반 일반 그래프 탐색 형태로도 구현 가능하지만, 상태 범위가 작고 고정이라 배열 기반이 훨씬 단순하고 빠르다.
• 양방향 BFS도 가능하지만 구현 복잡도가 올라가고, 이 문제 크기에서는 단방향 BFS로 충분하다.

2) BOJ 1926 - 그림

문제 핵심 요약

0과 1로 이루어진 n x m 격자에서, 상하좌우로 연결된 1 묶음을 그림 하나로 본다. 구해야 하는 값은:

1. 그림의 개수
2. 가장 넓은 그림의 넓이

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

격자에서 연결요소를 세는 전형 문제다. 방문하지 않은 1을 시작점으로 BFS를 돌리면 해당 그림의 넓이를 구할 수 있고, 이런 시작 BFS 횟수가 곧 그림 개수다.

즉,

• 바깥 이중 루프: 새 그림 시작점 찾기
• 내부 BFS: 해당 그림 넓이 계산
• maxArea 갱신

구조가 명확해서 실수 포인트를 줄이기 좋다.

시간/공간 복잡도

• 시간: O(nm) (각 칸 최대 1번 방문)
• 공간: O(nm) (visited 배열 + BFS 큐)

실수하기 쉬운 포인트

• 입력 직후 visited를 제대로 초기화하지 않는 실수
• 범위 체크(0 <= nx < n, 0 <= ny < m) 누락
• 그림이 하나도 없을 때 maxArea = 0 처리 누락

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

if (board[i][j] == 0 || visited[i][j]) continue;

새 BFS를 시작해야 하는 정확한 조건이다. 방문하지 않은 1에서만 시작한다.

if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (visited[nx][ny] || board[nx][ny] == 0) continue;

격자 BFS의 필수 안전장치다. 범위와 방문/값 조건을 분리해 가독성과 디버깅성을 높였다.

다른 풀이 가능성

• BFS 대신 DFS(재귀/스택)로 동일하게 풀 수 있다.
• 재귀 DFS는 입력이 클 때 스택 깊이 이슈가 있을 수 있어, 실전에서는 BFS나 반복형 DFS가 더 안정적이다.

오늘 정리 포인트:

• BFS는 “그래프 최단 경로”뿐 아니라 “격자 연결요소”에도 그대로 확장되는 기본 도구다.
• 문제를 받으면 먼저 상태를 어떻게 정의할지(정수 상태/격자 좌표) 정하면 구현이 빠르게 안정된다.