[백준][JAVA알고리즘]1149번 풀이(RGB거리) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1149번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1149 (RGB거리)

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

 

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

 

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

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

i(2 ≤ i ≤ N-1)N-1) 번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

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

제한

시간제한 : 0.5 초 (추가 시간 없음)

입력 예시

3
26 40 83
49 60 57
13 89 99

출력 예시

96

실패 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int min = Integer.MAX_VALUE;
	static int[][] house;
	static int N ;
	static int[] ch_rgb;
	static StringBuilder sb = new StringBuilder();
	static int temp = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		house = new int[N][3];
		ch_rgb = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			ch_rgb[i] = -1;
		}
		
		for(int i = 0 ; i < N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			if(st.hasMoreTokens()) {
				house[i][0] = Integer.parseInt(st.nextToken());
				house[i][1] = Integer.parseInt(st.nextToken());
				house[i][2] = Integer.parseInt(st.nextToken());
			}
		}
		
		rgb(0);
		

		System.out.println(min);
		
}
	public static void rgb(int depth) {
		
		if(depth == N) {
			min = Math.min(min, temp);
			return;
		}
		
		for(int i = 0 ; i < 3 ; i++) {
			ch_rgb[depth] = i;
			
			if(check(depth)) {
				
				temp += house[depth][i];
				
				rgb(depth+1);
				
				ch_rgb[depth] = -1;
				temp -= house[depth][i];
			}

		}
	}
	public static boolean check(int a) {
		
		//1번 집의 색은 2번 집의 색과 같지 않아야 한다.
		if(ch_rgb[0] == ch_rgb[1])
			return false;
		
		//N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
		if(ch_rgb[N-1] == ch_rgb[N-2] && ch_rgb[N-1] != -1)
			return false;
		
		//i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
		if(a!=0) {
		if(ch_rgb[a] == ch_rgb[a-1])
			return false;
		}
		
		return true;
	}

}

해당 코드가 굉장히 길죠?? 사실 해당 코드는 실패한 코드로... 시간 초과입니다. 곰곰이 봐보시면 그저 재귀를 이용한 방법으로 메모 이제이 션 기법을 사용하지 않았죠. 이것을 이제 메모이제이션으로 바꾸면 아래와 같게 됩니다.

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int min = Integer.MAX_VALUE;
	static int[][] house;
	static int[][] cost;
	static int N ;
	static StringBuilder sb = new StringBuilder();

	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		house = new int[N][3];
		cost = new int[N][3];

		for(int i = 0 ; i < N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			if(st.hasMoreTokens()) {
				house[i][0] = Integer.parseInt(st.nextToken());
				house[i][1] = Integer.parseInt(st.nextToken());
				house[i][2] = Integer.parseInt(st.nextToken());
			}
		}
		
		cost[0][0] = house[0][0];
		cost[0][1] = house[0][1];
		cost[0][2] = house[0][2];
		

		System.out.println(Math.min(Math.min(rgb(N-1,0), rgb(N-1,1)), rgb(N-1,2)));
}
	public static int rgb(int N, int color) {
		
		if(cost[N][color] == 0) {
			if(color == 0 ) 
				return cost[N][color] = Math.min(rgb(N-1,1), rgb(N-1,2)) + house[N][color];
			if(color == 1 ) 
				return cost[N][color] = Math.min(rgb(N-1,0), rgb(N-1,2)) + house[N][color];
			if(color == 2 ) 
				return cost[N][color] = Math.min(rgb(N-1,0), rgb(N-1,1)) + house[N][color];
		}
		
		return cost[N][color];
	
	}
}

이제 슬슬 동적 계획법에서 메모이제이션을 사용할 때 자주 사용되는 패턴을 알 수 있게 됩니다. RGB와 같이 새로운 함수를 정의하여 IF문으로 해당 값을 재귀해주면 해당 값은 반환해 주는 방식을 주로 사용하죠

 

즉, 일정 형식을 가지고 있다는 의미가 되죠

 

이제 STEP을 따라가면 쉽게 이해해 보도록 하죠

---

알고리즘 흐름도

 입력받기 -> RGB색깔 값 집어넣기 -> 가장 작은 값 구하기 -> 출력

---

STEP 1 RGB 값 이해하기

 해당 알고리즘을 풀기 위해서는 문제를 간단히 이해할 필요가 있습니다.

일단 RGB의 3가지 색감이 있고 집이 N개가 있습니다. 조건은 3가지를 만족하면 됩니다. 그런데 잘 생각해 보면 1, 2번 조건의 3번을 만족한다면, 뭐 당연히 만족하는 조건이죠.

 

즉 해당 문제는 N개의 집이 있는데 이웃하는 집들의 색은 다른 색이여야 한다라는 의미가 되죠.

그런데 여기서 입력으로 해당 색깔의 값을 지정해주어 최소 값을 찾으라는 문제입니다. 이렇게 최솟값을 찾으라는 의미는 즉, 모든 수를 비교해보아야 합니다.

 

에이 따라서 우선 해당 값들을 지정할 2차원 배열을 선언합니다.

house = new int[N][3];
		cost = new int[N][3];

		for(int i = 0 ; i < N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			if(st.hasMoreTokens()) {
				house[i][0] = Integer.parseInt(st.nextToken());
				house[i][1] = Integer.parseInt(st.nextToken());
				house[i][2] = Integer.parseInt(st.nextToken());
			}
		}
		
		cost[0][0] = house[0][0];
		cost[0][1] = house[0][1];
		cost[0][2] = house[0][2];

여기서 핵심은 house에다가 입력 값을 저장한다는 것이고

cost에는 각 첫 번째 집이 각각 R, G, B색깔일 때를 의미합니다.

 

가시적으로 보여드린다면

COST [0][0] => 첫 번째 집의 색깔이 R일 때

COST [0][1] => 첫 번째 집의 색깔이 G일 때

COST [0][2] => 첫 번째 집의 색깔이 B일 때

 

를 가리키게 되죠

---

STEP 2 메모이제이션을 이용하기 위한 패턴 찾기

 메모이제이션을 파악하기 위해서는 우선 패턴을 찾아야 합니다. 저희가 만든 2차원 배열 HOUSE를 살펴보도록 하죠.

	0	1	2
0	26	40	83
1	49	60	57
2	13	89	99
3
4

입력이 이런 식으로 들어오게 되었죠. 그렇다면 여기서 최소 값을 어떻게 찾아야 할까요.

 

저희는 COST에서 이미 첫 번째 집이 R, G, B일 때를 각각 넣어주었죠. 그렇다면, 그다음에 올 수 있는 인덱스는 무엇일까요?

 

(0,0)과 이어질 수 있는 수는 (1,1) 또는 (1,2)가 되죠 두 가지 수중에 더 작은 값을 고르면 되겠죠

 

즉, 열이 0일 때는 다음 행의 열이 1 또는 2가 되어야 하죠.

 

아직 이해가 안 되신다면 STEP 3을 보시면서 예제를 통해 이해해 보도록 하죠

---

STEP 3 메모이제이션 구현

public static int rgb(int N, int color) {
		
		if(cost[N][color] == 0) {
			if(color == 0 ) 
				return cost[N][color] = Math.min(rgb(N-1,1), rgb(N-1,2)) + house[N][color];
			if(color == 1 ) 
				return cost[N][color] = Math.min(rgb(N-1,0), rgb(N-1,2)) + house[N][color];
			if(color == 2 ) 
				return cost[N][color] = Math.min(rgb(N-1,0), rgb(N-1,1)) + house[N][color];
		}
		
		return cost[N][color];
	
	}

굉장히 간단합니다. N은 행을 나타내고 COLOR을 열을 나타냅니다. 

 

첫 IF조건문을 통해서 메모이제이션을 판별해 주었죠. 해당 배열에 값이 없다면, 즉, 재귀가 행해지지 않았다면, 재귀를 해주라는 조건입니다.

 

재귀의 조건은 3개입니다. 색깔이 빨강, 초록, 파랑일 때를 각각 나누어줍니다. 물론 최솟값을 반환받도록 하죠. 둘 중의 값 중에 더 싼값을 찾아주는 Math.min을 활용해서 말이죠.

 

뒤에 있는 house는 현재 인덱스가 가리키는 색깔의 값을 더해주는 방식으로요.

말로만 하니 이해가 되기 어려우시죠??

 

입력 예시로 보여드리겠습니다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

cost에 들어있는 값 (cost [3][3])

26 40 83

0   0   0

0   0   0

house에 들어있는 값 (house [3][3])

26 40 83

49 60 57

13 89 99

 

--------------------------------------------

이제 들어가 봅니다. 각 rgb함수에 첫 번째 값일 때를 넣어줍니다.

rgb(2,0), rgb(2.1), rgb(2,2)가 각각 실행이 됩니다.

 

rgb(2,0)

cost [2][0]에는 값이 비어있기에 if문을 실행해 줍니다. 색깔은 0 빨강이기에 첫 if문을 실행해 줍니다.

return cost [2][0] = Math.min(rgb(1.1), rgb(1.2)) + house [2][0]을 해줍니다. 그럼 그전에

 

rgb(1,1)

return cost [1][1] = Math.min(rgb(0,0), rgb(0,2)) + house [1][1];

 

rgb(1,2)

return cost [1][2] = Math.min(rgb(0,0), rgb(0,1)) + house [1][2];

 

이런 식으로 들어가게 되죠. 이제 마지막 rgb(0,?)이 값들은 모두 앞서 저희가 임의로 넣어준 cost에 0이 아닌 값이 있기에 해당 값을 그냥 바로 반환해 줍니다. 그렇게 역으로 올라가 보도록 하죠.

rgb(1,1)

return cost [1][1] = Math.min(26, 83) + 60; 즉, 86이 됩니다.

 

rgb(1,2)

return cost [1][2] = Math.min(26, 40) + 57; 즉, 83이 됩니다.

 

rgb(2,0)

return cost [2][0] = Math.min(86, 83) +13을 해줍니다. 그러면 96이 나오게 되죠. 이런 식으로 나머지 rgb값도 계산이 되게 됩니다. 우선 빨간색이 처 음색일 때를 봤었죠 그렇다면 이제 cost에는 해당 값들이 넣어지게 됩니다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

cost에 들어있는 값 (cost [3][3])

26 40 83

0   86 83

96   0   0

house에 들어있는 값 (house [3][3])

26 40 83

49 60 57

13 89 99

--------------------------------------------

 

이제 좀 이해가 되시겠죠~? 이런 식으로 계산이 되어 결국에는 cost에 있는 마지막 행의 줄에 있는 값들을 비교하여, 최소 값을 비교하면, 저희가 원하는 최솟값을 얻을 수 있게 됩니다.

---