다이나믹 프로그래밍 [BOJ] 1149 RGB거리

---

온라인 알고리즘 문제 풀이에 재미를 붙여가던 중, 처음으로 난관에 부딪힌 문제였다.

https://www.acmicpc.net/problem/1149

문제는 간단하게 다음과 같다.

1. 개의 집이 일렬로 이루어진 배열 형태의 마을이다.

2. 와 , 와 은 이웃이고, 와 는 이웃이 아니다.

3. 각 집은 빨강(R), 초록(G), 파랑(B)의 색 중 하나를 골라 칠한다.

4. 이웃한 집은 같은 색으로 칠할 수 없다.

5. 모든 집을 칠하는 총 비용이 최솟값이어야 한다.

6. 비용은 다음과 같이 주어진다. 

	R 비용	G 비용	B 비용
	26	40	83
	49	60	57
	13	89	99

7. 해당 예제의 정답은 (26) +  (57) + (13) = 96이다.

풀이 과정

최초 문제 풀이는 단순한 Math.min() 계산을 이용했다.

당연히 이렇게 간단하게 해결될 것이라고는 생각 하지 않았다.

이 때 당시에는 DP의 존재조차도 모르는 상태였기 때문에, 솔루션을 찾아내기란 거의 불가능에 가까웠다.

이런식으로 풀면 거스름돈 예제로 유명한 Greedy Algorithm (탐욕 알고리즘)에 빠지게 된다.

import java.util.Scanner;
 
public class Main {
    static int minimum = 0;
    
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        
        int T = scan.nextInt();
        int red, green, blue;
        int next_fst=0, next_snd=0;
        int result=0;
        
        for(int i=0; i<T; i++){
            red = scan.nextInt();
            green = scan.nextInt();
            blue = scan.nextInt();
            
            if(i==0){
                if(min(red, green, blue)==red){
                    result += red;
                    minimum = 1;
                } else if(min(red, green, blue)==green){
                    result += green;
                    minimum = 2;
                } else{
                    result += blue;
                    minimum = 3;
                }
            }
            else{
                if(minimum == 1){
                    if(min(green, blue) == green){
                        minimum = 2;
                        result += green;
                    } else{
                        minimum = 3;
                        result += blue;
                    }
                }
                else if(minimum == 2){
                    if(min(red, blue) == red){
                        minimum = 1;
                        result += red;
                    } else{
                        minimum = 3;
                        result += blue;
                    }
                }
                else{
                    if(min(red, green) == red){
                        minimum = 1;
                        result += red;
                    } else{
                        minimum = 2;
                        result += green;
                    }
                }
            }
        }
        
        System.out.println(result);
        
    }
    
    public static int min(int r, int g, int b){
        
        if(r<=g && r<=b) return r;
        else if(g<=b && g<= r) return g;
        else return b;
    }
    
    public static int min(int first, int second){
        if(first<=second) return first;
        else return second;
    }
}

최초 코드의 모습이다.

if - else 가 난무하고 결과적으로 결과값도 틀리다.

이에 해결책으로 머릿속에 Backtracking (백트래킹)을 떠올렸고, 나름 철저하게 설계를 한 내용이다.

 *  최초 Solution. (2016-10-24)
 *  문제점 : 탐욕적 알고리즘으로 실행됨.
 *  해결책 : 1 2 3
 *         4 100 200
 *         5 6 7
 *  이 test case를 적용할 수 있어야 한다.
 *  --> Back Tracking을 사용해본다.
 *  
 *  Step 1. main의 if~else를 '재귀적' 으로 바꿔서 간소화한다.
 *  Step 2. min() method 에서 재귀처리와 가지치기가 가능한지 생각한다.
 *  Step 3. 첫 번째 집에서 어떤 색을 선택하느냐에 따라 그 이후로 '완전 이진 트리' 가 된다. 이를 고려한다.
 *  Step 4. 그렇다면 i=0 일 때와 i=1 ~ i<n 일때를 분리한다.
 *  Step 5. 1st house 에서 어떤 색을 고르는지, 그에 따른 minimum 값을 배열에 넣는다.
 *  Step 6. 배열 값을 비교하여 최솟값중의 최솟값을 찾는다.

하지만 이미 머릿속에서조차 정리도 안된 내용을 코드로 구현 가능할리 만무했다.

 *  문제점 : 입력과 함수호출에서 뭔가 혼란이 발생했다.
 *  해결책 : 그냥 입력값을 2차원 배열에 저장하고, 이상태에서 탐색해본다.
 *  
 *  Step 1. 입력값을 2차원 배열에 저장한다.
 *  Step 2. i=0일때, R(0,1) G(0,2) B(0,3) 이므로, i=1일때 부터는 이전 j를 고려하여 탐색한다.
 *  Step 3. 이전 j값을 변수 prev_j에 저장하여 비교한다.
 *  Step 4. if(j==prev_j) -> continue; else min(one, two);
 *  Step 5. 3중 for문이 될 것 같은데.. time limit에 걸리지 싶다.
 *  Step 6. 일단 생각해 본 뒤 구현해보자.

못했다는 말이다.

결국 다시 첫 구현 코드에서 수정하는 방식으로 돌아가게 됐다.

약간 하드코딩 식으로 수정하면서 원하는 결과값이 나오는 Test case가 점점 늘어났고, 왠지 답이 맞을 것 같다는 느낌도 받았다.

 *  문제점 : 예제 Test Case와 1 2 3 / 4 100 200 / 5 6 7 Test Case는 값이 잘 나온다.
 *  해결책 : 어떤 Test Case일 때 출력이 틀릴지 생각해본다.
 *  .....문제점 발견
 *  1 10 100
 *  100 5 50
 *  100 20 100
 *  의 Case를 생각해보자.
 *  실제 답은 1, 50, 20 = 71 이지만,
 *  현재 알고리즘으로는 10, 50, 20 = 80 으로 나타난다.
 *  Why? min() method 때문이다.
 *  
 *  해결책 : 아예 두 수 비교가 아닌 전체 case를 다 검사해야 하는 것 같다.

하지만 예외 케이스를 찾아냈다.

public class Main {
 
    static int rgb[][];
    static int next_fst=-1, next_snd=-1; // R=0, G=1, B=2
    static int before_j=-1;
    
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        
        int T = scan.nextInt();
        long result=0;
        long minimum=0;
        
        rgb = new int[T][3];
        
        for(int i=0; i<T; i++){
            rgb[i][0] = scan.nextInt();
            rgb[i][1] = scan.nextInt();
            rgb[i][2] = scan.nextInt();
        }
        
        for(int k=0; k<3; k++){
            result=0;
            next_fst=-1;
            next_snd=-1;
        for(int i=0; i<T; i++){
            if(next_fst!=-1 || next_snd!=-1)
                result += min(rgb[i][next_fst], rgb[i][next_snd]);
            
            if(i==0){
                if(k==0){
                    next_fst = 1;
                    next_snd = 2;
                } else if(k==1){
                    next_fst = 0;
                    next_snd = 2;
                } else{
                    next_fst = 0;
                    next_snd = 1;
                }
                result+=rgb[i][k];
            } else{
                if(before_j==0){
                    next_fst = 1;
                    next_snd = 2;
                } else if(before_j==1){
                    next_fst = 0;
                    next_snd = 2;
                } else{
                    next_fst = 0;
                    next_snd = 1;
                }
                
            }
                
        }
        if(k==0) minimum=result;
        if(minimum>result) minimum=result;
        }
        
        System.out.println(minimum);
        
    }
    
    public static int min(int first, int second){
        if(first<=second){
            before_j = next_fst;
            return first;
        } else {
            before_j = next_snd;
            return second;
        }
    }
}

직접 손으로 코드를 디버깅해보면, min() method의 한계로 인해 틀린 결과값이 나오는 것을 알 수 있다.

수많은 시행착오 끝에 dp의 존재를 알게 됐고, 이 문제는 dp 맞춤형이며 그동안 열심히 생각했던 그 어떤 나의 접근 방법도 이 문제를 해결할 수 없음을 깨달았다.

 *  해결책 : i=0부터 가지를 흩뿌리며 이진트리로 탐색하는 문제가 아니었다.
 *  이 문제는 확실히 dp 문제이며, 해결책은 다음과 같다.
 *  <위의 실패한 test case를 이용한다.>
 *  
 *  1) i=0일 때.
 *      dp[0][0] = 1, dp[0][1] = 10, dp[0][2] = 100 을 저장한다.
 *  2) i=1일 때.
 *      dp[1][0] = 100 + min(dp[0][1], dp[0][2])
 *      dp[1][1] = 5 + min(dp[0][0], dp[0][2])
 *      dp[1][2] = 50 + min(dp[0][0], dp[0][1])
 *  3) i=2일 때.
 *      dp[2][0] = 100 + min(dp[1][1], dp[1][2])... 이런식이다.
 *  
 *  --------> 접근 방법 자체가 잘못되었었다.
 *            dp의 핵심은 '해'를 배열에 저장하고 이를 '이용'하는 것이다.
 *            항상 머릿속에 박아두자.

심지어는 dp도 처음에 이해를 잘못해서 dp를 그냥 배열의 이름으로 사용하기만 할 뿐 풀이법에 변화를 주지 않았다.

> 이를 뒤늦게 깨닫고 dp란 '해'를 미리 저장하고 '이용' 해먹는 것이라는 걸 알게됐다.

import java.util.Scanner;
 
public class Main {
 
    static int rgb[][];
    static int dp[][];
    
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        
        int T = scan.nextInt();
    
        rgb = new int[T][3];
        dp = new int[T][3];
        
        for(int i=0; i<T; i++){
            rgb[i][0] = scan.nextInt();
            rgb[i][1] = scan.nextInt();
            rgb[i][2] = scan.nextInt();
        }
 
        for(int i=0; i<T; i++){
            if(i==0){
                dp[i][0] = rgb[i][0];
                dp[i][1] = rgb[i][1];
                dp[i][2] = rgb[i][2];
            } else{
                dp[i][0] = rgb[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
                dp[i][1] = rgb[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
                dp[i][2] = rgb[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
            }
        }
        
        System.out.println(Math.min(dp[T-1][0], Math.min(dp[T-1][1], dp[T-1][2])));
        
    }
}

최종 완성본이다.

DP는 정말 많은 시행착오를 겪고 거의 다섯번 정도 새로 코드를 갈아 엎으며 얻은 소중한 지식이다.

이 문제풀이를 절대 잊지 않고 앞으로 만날 수많은 dp 문제들을 콧방귀 끼며 풀어야겠다.