[백준] #17404번 RGB거리2 (C++)

문제

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

RGB 거리1 풀어보기 (반복문 -> 재귀)

먼저 이 문제를 풀기 전 RGB거리 1문제를 풀어봤는데 R, G, B에 해당하는 총 3가지의 케이스에 대해서만 고려하면 되므로 N만큼 반복문을 돌려 3개의 케이스에 대해 아래와 같은 조건문과 점화식으로 쉽게 풀 수 있었다.

반복문 풀이

if (k == 0) {  // k는 R, G, B를 나타냄
	dp[i][k] += min(dp[i - 1][k + 1], dp[i - 1][k + 2]);
}
else if (k == 1) {
	dp[i][k] += min(dp[i - 1][k - 1], dp[i - 1][k + 1]);
}
else {
	dp[i][k] += min(dp[i - 1][k - 2], dp[i - 1][k - 1]);
}

하지만.. 만약 케이스가 3가지 이상이거나 다른 조건이 붙는다면 조건문이 굉장히 난잡해질 수 있다.
그러한 경우 위 방법보다는 재귀로 푸는 것이 더 직관적일 것 같아 재귀로도 나타내보았다.

재귀 풀이

// 깊이, 이전 색
int dfs(int depth, int pre) {

	if (depth == n) return 0;

	if (dp[depth][pre] != -1) return dp[depth][pre];

	int result = INT_MAX;

	for (int i = 0; i < 3; i++) {
		if (i != pre) {
			result = min(result, rgb[depth][i] + dfs(depth + 1, i));
		}
	}
	
	// 이전 색칠 값의 정보를 저장하여 중복 연산을 방지한다.
	dp[depth][pre] = result;
	
	return result;
}

재귀로 풀 때 주의할 점은 위와 같은 재귀 연산은 곧 완전 탐색과 같으므로 중복 연산이 발생하지 않도록 메모이제이션을 해줘야 된다는 점이다.

RGB 거리2 재귀로 풀어보기

RGB거리 2 문제는 RGB 거리1에서 아래의 조건이 하나 추가된 문제이다.

N번 집의 색은 1번 집의 색과 같지 않아야 한다.

사실 굳이 재귀를 이용하지 않고 반복문으로도 쉽게 해를 구할 수 있다.
(1번집의 3가지 케이스에 대한 반복문에서 위 반복문 풀이를 감싸주면 1번 집이 칠한 색을 알 수 있다)

우선 1번 집의 색을 알기위해 마찬가지로 3가지 케이스에 대한 반복문을 통해 재귀함수를 호출하였다.

재귀함수를 호출할 때는 위에서 추가된 조건을 처리하기 위해 1번 집의 색을 나타내는 인덱스 또한 별도로 매개변수에 전달해주었다.

주의할 점은 각각의 3가지 케이스에 대해 독립적으로 해를 구하는 것이기 때문에 캐시 배열 또한 각각의 케이스마다 초기화 해줘야 된다는 점이다.

안그러면 1번 케이스에서 할당된 캐시배열로 인해 2번 케이스에서 다른 경우의 수임에도 불구하고 중복 계산으로 오인하여 엉뚱한 해를 구하게된다.

그리고 재귀함수에서 depth가 마지막 집(N)까지 도달했을 때는 따로 추가된 조건을 처리해주도록 한다.

RGB 거리2 전체 코드

#include<iostream>
#include<algorithm>
#include<limits.h>

using namespace std;

int n;
int rgb[1001][3];
int dp[1001][3];

// 깊이, 이전 색, 시작 색
int dfs(int depth, int pre, int start) {

	if (depth == n) return 0;

	if (dp[depth][pre] != -1) return dp[depth][pre];

	int result = INT_MAX;

	for (int i = 0; i < 3; i++) {
		if (depth == n - 1) { // 추가된 조건 처리!
			if (i != pre && i != start) {
				result = min(result, rgb[depth][i] + dfs(depth + 1, i, start));
			}
			else continue;
		}
		else {

			if (i != pre) {
				result = min(result, rgb[depth][i] + dfs(depth + 1, i, start));
			}
		}
	}
	
	// 이전 색칠 값의 정보를 저장하여 중복 연산을 방지한다.
	dp[depth][pre] = result;
	
	return result;
}


int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int k = 0; k < 3; k++) {
			cin >> rgb[i][k];
			dp[i][k] = -1;
		}
	}
	int result = INT_MAX;

	for (int i = 0; i < 3; i++) { // 1번 집의 색을 나타냄
    
		for (int i = 0; i < n; i++) {
			for (int k = 0; k < 3; k++) {
				dp[i][k] = -1;
			}
		}

		int temp = dfs(1, i, i) + rgb[0][i];
		result = result > temp ? temp : result;
	}

	cout << result;
}

DP 배열 초기화 잊지말자