1. 문제 정보
- 문제 요약: 개의 집을 빨강, 초록, 파랑 중 하나의 색으로 칠해야 합니다. 인접한 집끼리는 색이 달라야 하는데, 이 문제의 핵심은 1번 집과 번 집도 이웃으로 간주한다는 점입니다. 즉, 집들이 원형으로 배치된 구조입니다.
- 난이도: Gold 4
- 링크: https://www.acmicpc.net/problem/17404
2. 접근 방식
2.1 문제의 본질: 원형 구조의 딜레마
이 문제는 'RGB거리 1' 문제와 비슷해 보이지만, "1번 집과 번 집의 색이 달라야 한다"는 조건 하나 때문에 난이도가 급상승합니다.
기본적인 선형 DP에서는 번째 집의 색을 결정할 때 번째 집만 고려하면 됐습니다. 하지만 원형 구조에서는 첫 번째 집의 선택이 마지막 집에 영향을 주고, 마지막 집의 선택이 다시 첫 번째 집과 충돌하지 않아야 하는 순환 의존성이 발생합니다.
이 고리를 끊지 않으면, 점화식을 세울 수 없습니다.
2.2 알고리즘 설계: 선형 환원
순환 문제를 해결하는 가장 확실한 방법은 임의의 한 지점을 고정(Fix)하여 선형 문제로 만드는 것입니다.
- 첫 집의 색을 고정합니다. (예: 1번 집 = Red)
- 이제 1번 집의 색이 정해졌으므로, 2번 집부터 번 집까지는 일반적인 'RGB거리' 문제(선형 DP)와 똑같이 풀 수 있습니다.
- 마지막 검증: 수행이 끝난 후, 번 집의 색이 1번 집의 색(Red)과 겹치지 않는 경우만 정답 후보로 채택합니다.
- 이 과정을 1번 집이 Green일 때, Blue일 때 각각 반복하여 총 3번의 DP를 수행합니다.
2.3 점화식 및 수식
를 "번째 집을 색(0:R, 1:G, 2:B)으로 칠했을 때의 최소 비용"이라고 정의합시다.
점화식은 다음과 같습니다:
여기서 중요한 테크닉은 초기화입니다. 첫 집을 특정 색(예: Red)으로 고정했다면, 다른 색(Green, Blue)으로 시작하는 경우는 불가능하므로 비용을 INF로 설정하여 선택되지 않도록 막아야 합니다.
3. 코드 구현
3.1 실패한 코드 (Backtracking - 시간 초과)
처음에는 직관적인 백트래킹(DFS)으로 접근했습니다. 하지만 이 최대 1,000이므로 지수 시간 복잡도를 가지는 완전 탐색은 불가능합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class BOJ_17404_백트래킹_시간초과 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N;
static int[][] cost;
static int[] color;
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
cost = new int[N + 1][3];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
cost[i][j] = Integer.parseInt(st.nextToken());
}
}
color = new int[N + 1];
Arrays.fill(color, -1);
solv(1, 0);
System.out.println(answer);
}
private static void solv(int idx, int value) {
if (idx == N) {
for (int i = 0; i < 3; i++) {
if (color[idx - 1] != i && color[1] != i) {
answer = Math.min(answer, value + cost[idx][i]);
}
}
return;
}
for (int i = 0; i < 3; i++) {
if (color[idx - 1] != i) {
color[idx] = i;
solv(idx + 1, value + cost[idx][i]);
color[idx] = -1;
}
}
}
}
3.2 정답 코드 (DP - 통과)
첫 집의 색을 고정하는 루프(color)를 가장 바깥에 두고, 내부에서 선형 DP를 수행합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class BOJ_17404 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N;
static int[][] cost;
static int[][] dp;
static final int INF = 10_000_001;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
cost = new int[N][3];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
cost[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new int[N][3];
// 초기화를 여기서 전체적으로 하지 않고, 각 loop 시작 시점에 처리
int answer = Integer.MAX_VALUE;
// 1번 집의 색을 0(R), 1(G), 2(B)로 고정하며 3번 반복
for (int color = 0; color < 3; color++) {
Arrays.fill(dp[0], INF); // 일단 모두 INF로 초기화
dp[0][color] = cost[0][color]; // 고정된 색만 실제 비용 대입
for (int i = 1; i < N; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
}
// 원래 코드 로직 유지: dp[0][color]를 다시 INF로 돌리는 부분은
// 다음 루프에 영향을 주지 않으므로(매번 새로 초기화하거나 덮어씀)
// 사실상 현재 로직에서는 큰 의미는 없으나 원본 존중
dp[0][color] = INF;
// 마지막 집(N-1)의 색이 처음 고정한 색(color)과 달라야 함
answer = Math.min(answer, Math.min(dp[N - 1][(color + 1) % 3], dp[N - 1][(color + 2) % 3]));
}
System.out.println(answer);
}
}
4. 회고 및 배운 점
-
실패 원인 (Backtracking): 개의 집을 칠하는 경우의 수는 대략 개입니다. 일 때 은 우주가 멸망해도 계산이 끝나지 않는 수치입니다. 따라서 '시간 초과(TLE)'는 필연적이었습니다.
-
성공 이유 (DP): DP는 한 번 방문한 상태를 저장(Memoization)하므로, 집의 개수 에 비례하는 의 시간 복잡도를 가집니다. 첫 집을 고정하기 위해 3번 반복하더라도 으로 충분히 빠릅니다.
