BOJ 풀이 노트: 색약 구역 BFS와 스티커 DP 정리

2026. 3. 23. · tech

오늘은 BOJ 10026과 9465를 묶어, 상태 정의를 단순화한 BFS 구역 탐색과 인접 제약을 반영한 2행 DP 전이를 실수 포인트 중심으로 정리했다.

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

• BOJ 10026 - 적록색약
• BOJ 9465 - 스티커

두 문제 모두 구현 자체는 길지 않지만, 조건을 상태로 어떻게 바꾸느냐가 핵심인 유형이다.

1) BOJ 10026 - 적록색약

문제 핵심 요약

N×N 색상 격자에서 연결된 구역 수를 세는 문제다. 일반 시야 기준 구역 수와, 적록색약 시야(R/G를 동일 색으로 인식) 기준 구역 수를 각각 구해 출력한다.

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

핵심은 “같은 색으로 간주되는 칸들”의 연결 요소 개수를 세는 것이다. 따라서 BFS/DFS로 연결 요소 카운팅이 정석이다.

이번 구현에서는 같은 BFS를 두 번 돌린다.

• 일반 모드: 문자 완전 일치(R==R, G==G, B==B)
• 색약 모드: R과 G를 같은 그룹으로 취급

별도 격자를 만들지 않고 sameColor(a, b, colorWeak) 함수에서 비교 규칙만 바꿔 재사용했다.

시간/공간 복잡도

• 시간: O(N^2) (각 모드에서 모든 칸을 한 번씩 방문)
• 공간: O(N^2) (방문 배열 + 큐)

실수하기 쉬운 포인트

• 색약 모드에서 R/G를 한쪽 방향으로만 처리하는 실수 (R->G만 허용 등)
• BFS 시작 기준 색을 고정하지 않고, 이웃끼리만 비교해서 잘못 확장되는 실수
• 모드 전환 시 방문 배열 초기화를 빼먹는 실수

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

if ((a == 'R' || a == 'G') && (b == 'R' || b == 'G')) return true;

색약 모드에서 R/G를 동일 그룹으로 묶는 조건이다.

if (!sameColor(base, grid[nr][nc], colorWeak)) continue;

BFS 확장 판단 기준을 함수로 통일해 일반/색약 두 모드를 같은 로직으로 처리한다.

다른 풀이 가능성

• BFS 대신 DFS(재귀/스택)로 동일하게 해결 가능하다.
• 색약용으로 격자를 미리 변환(G -> R)한 뒤 일반 카운팅 1회로 처리하는 방법도 있다.

2) BOJ 9465 - 스티커

문제 핵심 요약

2행 N열 스티커 점수가 주어질 때, 변을 공유하는 스티커를 동시에 선택할 수 없다는 제약 하에 점수 합의 최댓값을 구하는 문제다.

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

열 단위로 보면, 어떤 열의 윗칸을 고르면 같은 열 아랫칸/좌우 인접칸 제약이 생긴다. 따라서 **“i열에서 위/아래를 선택했을 때의 최대값”**으로 DP를 잡으면 전이가 단순해진다.

• dp[0][i]: i열 위 스티커를 선택했을 때 최대 점수
• dp[1][i]: i열 아래 스티커를 선택했을 때 최대 점수

전이는 다음처럼 잡는다.

• dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + a[0][i]
• dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + a[1][i]

즉, 같은 행 인접 선택을 피하면서 직전/직전직전의 반대 행 최적값을 이어받는다.

시간/공간 복잡도

• 시간: O(N) (테스트케이스당)
• 공간: O(N)

실수하기 쉬운 포인트

• i=1, i=2 초기값 처리 누락으로 인덱스 에러가 나는 실수
• 전이를 max(dp[1][i-1], dp[0][i-1])처럼 잘못 써서 같은 열/행 제약을 깨는 실수
• 테스트케이스마다 DP 배열 초기화를 안 해서 이전 케이스 값이 섞이는 실수

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

dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + a[0][i];

위 스티커를 고를 때 가능한 직전 상태(반대 행)만 받도록 만든 핵심 전이다.

cout << max(dp[0][n], dp[1][n]) << '\n';

마지막 열에서 위/아래 중 최댓값이 정답이다.

다른 풀이 가능성

• 상태를 3개(선택 안 함/위 선택/아래 선택)로 두는 DP도 가능하다.
• 메모리 최적화를 위해 i-1, i-2만 유지하는 롤링 배열 형태로 줄일 수도 있다.

오늘 정리 포인트:

• 그래프 문제는 “연결 요소”로 해석되는 순간 BFS/DFS로 빠르게 안정화된다.
• DP 문제는 제약을 상태 정의에 녹여내면 전이식이 짧아지고 실수도 줄어든다.