[백준] 1149번 C/C++ 풀이 _ RGB 거리

 


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

시간 제한메모리 제한제출정답맞은 사람정답 비율
0.5 초 (언어별 추가 시간 없음)128 MB197438531641447.311%

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

예제 입력 

3
26 40 83
49 60 57
13 89 99

예제 출력 

96

힌트

출처

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: djm03178
  • 데이터를 추가한 사람: rdd6584

알고리즘 분류

>> 문제 풀이 

dfs 를 이용하여 구현하였다. 
하지만 매 단계 깊이가 진행할수록 2개의 자식 노드를 가지기 때문에, 백트래킹을 이용해야한다. 

그대로 진행할 경우 21000번 만큼을 수행해야 한다다. 

 

지금까지 거쳐온 노드들의 합을 저장하는 배열 mini_val 을 선언한다. 
mini_val[level][i] 는 level 높이까지 지나오면서 level 높이의 색이 i를 가진 가장 최소의 값이다. 

만약 이 값보다 작거나 같은 값을 가지고 있으면 , 이 노드부터는 동일한 경로를 지나기 때문에 굳이 dfs를 수행할 필요가 없다. 

원리는 간단한데 세세한 구현에서 조금 막혀서 시간이 소비되었다. 

여담 : 아직은 dfs와 dp 의 정확한 구분을 잘 못하겠다. ... 뭘 보고 dp 라고 느껴야 하는것인가??

>> 다른풀이

굳이 dfs를 쓸 필요 없이 각 높이별로 (bfs ) 같은 느낌으로 다음 단계의 누적 합을 갱신해준다. 
이를 반복해서 수행하면 O(높이) 만큼의 시간 복잡도가 소요된다. 

d[i][0] = Min(d[i-1][1], d[i-1][2]) + a[i][0]; 
d[i][1] = Min(d[i-1][0], d[i-1][2]) + a[i][1]; 
d[i][2] = Min(d[i-1][0], d[i-1][1]) + a[i][2];

위의 점화식을 지속적으로 갱신하는 것이다. 

>> 소스 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#define MAX 987654321
using namespace std
#pragma warning(disable: 4996)
 
int N;
int color_val[1000][3];
int mini_val[1000][3];
int mini = MAX;
 
void dfs(int level, int nowNum, int sum) {
    // 합이 최소값보다 크면 종료 
    if (sum > mini) return
 
    // 끝에 도달하면 종료
    if ( level == N ) {
        if (sum < mini) mini = sum;
        return;
    }
 
    for (int i = 0; i < 3; i++) { 
        // 색이 같으면 그냥 넘겨 
        if (i == nowNum) continue
 
        // 방문한 곳의 값이 더 작거나 같으면 종료 
        if ( (mini_val[level][i] <= sum + color_val[level][i] )  ) continue;
        else mini_val[level][i] = sum + color_val[level][i]; 
        
        // 다음 단계 
        dfs(level+1, i, mini_val[level][i]);
    }
}
 
int main() {
    // 숫자 입력 받기 
    cin >> N;
    forint k = 0 ; k < N; k++){
        for (int i = 0; i < 3; i++) { 
            scanf"%d" , &color_val[k][i]);
            mini_val[k][i] = MAX;
        }
    }
 
    for (int i = 0; i < 3; i++) {
        mini_val[0][i] = color_val[0][i]; 
    }
    for (int i = 0; i < 3; i++) {  
        dfs( 1 , i , color_val[0][i]);
    }
 
    cout << mini;
 
    return 0
}
cs