[백준] 1149번 : RGB거리 - JAVA[자바]

www.acmicpc.net/problem/1149

1149번: RGB거리

 

---

• 문제

 

 

 

이번 문제는 조금은 생각해 볼 필요가 있는 문제인 것 같다. 대표적으로 풀이방법이 2가지가 있는데, 재귀(Top-Down)방법과 반복문(Bottom-Up)을 이용한 방법. 이렇게 두 가지로 나뉜다. 여타 다른 문제처럼 먼저 재귀를 이용한 풀이를 보여주고, 마지막에 반복문을 사용한 풀이 방법을 알려주겠다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

먼저 문제에 대한 이해가 필요하다.

 

풀이 조건이 조금은 어렵게 설명되어 있는데, 간단하게 설명하자면 다음과 같다.

일단 각각의 집을 색칠해야하고, 색의 종류는 3가지가 주어진다 (빨간색, 초록색, 파란색). 그리고 각 집마다 해당 색을 칠하는 비용이 주어진다. 그리고 전체 집을 색칠 할 때 최소 비용을 구하는 것이다.

 

이때 중요한 점이라면 인접한 집끼리는 색이 겹치면 안된다는 점이다. 

예로들어 3번 집에 초록색을 칠한다면, 2번집과 4번집은 초록색을 칠 할 수 없다. 이러한 조건으로 인해 주로 실수하는 점이 비용을 구할 때 그냥 최솟값만을 찾아서 하면 틀린다.

 

무슨말인고 하니 예로들어 이러한 케이스가 있다고 가정해보자

 

만약 각 집마다 최솟값을 찾아 누적합을 하면 다음과 같은 일이 생긴다.

 

1번 집 최솟값 = 1

 

 

인접한 집끼리는 같은 색을 칠 할 수 없으므로 2번 집의 초록색과 파란색 중 최솟값을 찾아 누적합. 즉 103 + 1

 

 

이전 집이 초록색이였으므로 빨간색 집과 파란색 집 중 최솟값을 누적합. 즉 100 + 104

 

 

즉, 위와같이 하면 출력은 204가 되겠지만 이게 정답인가?

아니다.

 

사실 정답은 100(1번집 Green) + 1(2번집 Red) + 1(3번집 Green)인 102가 정답이다. 즉 각 집별 최솟값이 아닌 아래 그림과 같은 빨간색 칸을 선택해야 올바른 정답이 된다.

 

 

 

결과적으로 각 집의 최솟값을 찾아 누적합을 구하는 것이 아닌 모든 경로의 경우의 수를 찾아서 최종적으로 작은 누적합을 찾아야 한다.

 

각 집의 비용을 Cost라고 할 때 이를 한 단계씩 적어보면 다음과 같다. (이때 min은 두 개의 값 중 최솟값을 의미하며 += 은 누적합이다.)

 

 

즉, 점화식으로 본다면 N에 대하여 세 가지 케이스에 대해 다음과 같다.

 

Red일 경우

Cost[N][0] = min( Cost[N-1][1], Cost[N-1][2] ) + Cost[N][0]

 

Green일 경우

Cost[N][1] = min( Cost[N-1][0], Cost[N-1][2] ) + Cost[N][1]

 

Blue일 경우

Cost[N][2] = min( Cost[N-1][0], Cost[N-1][1] ) + Cost[N][2]

 

 

 

 

점화식을 알았으니 동적계획법으로는 어떻게 풀이해야하는가만 남았다.

기본적으로 이전의 문제들 (01타일, 피보나치 수 등..)과 같은 알고리즘을 사용하면 된다. 다만 3가지 케이스를 이용해야하니 Cost[][] 배열과, 탐색하면서 누적합을 저장할 DP[][] 함수를 두면 된다. 그리고나서 위 점화식을 이용하여 재귀함수로 구성한 뒤, 해당 배열을 아직 탐색하지 않았다면 재귀를 해주고, 그 외의 경우는 DP배열의 값을 반환해주면 된다.

 

즉, 다음과 같이 짜면 된다. (참고로 각 비용은 자연수로 입력된다고 하니 DP배열을 -1로 초기화 해줄 필요 없이 탐색하지 않은 경우를 초기값(0)으로 쓰면 된다.)

 

int[][] Cost = new int[N][3];	// 이미 입력값들로 초기화가 되었다고 가정

int[][] DP = new int[N][3];

// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
DP[0][Red] = Cost[0][Red];	
DP[0][Green] = Cost[0][Green];
DP[0][Blue] = Cost[0][Blue];

	
static int Paint_cost(int N, int color) {

	// 만약 탐색하지 않은 배열이라면
	if(DP[N][color] == 0) {
			
		// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
		if(color == Red) {
			DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
		}
		else if(color == Green) {
			DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
		}
		else {
			DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
		}
			
	}
		
	return DP[N][color];
}

 

 

 

이렇게 짜면 이후 다른 색에 대하여 탐색을 할 때 이전에 탐색했던 값의 경우 더이상 재귀호출 해줄 필요 없이 바로 해당 DP의 인덱스 값을 재활용하면 되기 때문에 동적계획법에도 알맞은 알고리즘일 것이다.

 

이렇게 하나의 함수를 만들고 Paint_cost(N, Red), Paint_cost(N, Green), Paint_Cost(N, Blue) 을 호출하여 해당 반환 값 중 최솟값을 출력해주면 된다.

 

 

 

반복문으로 풀이하는 방법은 마지막에 풀이하면서 설명해주겠다.

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

알고리즘은 위에서 설명한 재귀 방법과 반복문으로 풀이하는 법, 두 가지 방법을 보여줄 것이다. 그리고 입력의 방법 (BufferedReader, Scanner)에 따라 성능의 차이 또한 볼 것인데, 동적계획법 카테고리인 만큼 동적계획법 알고리즘에서 Scanner와 BufferedReader을 사용한 방법을 보여줄 것이고, 반복문은 BufferedReader로만 풀 것이다.

 

즉, 다음과 같은 세 가지 방법을 보여줄 것이다.

 

1 . 재귀 + Scanner

2. 재귀 + BufferedReader

3. 반복문 + BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [재귀 + Scanner]

 

import java.util.Scanner;

public class Main {
	
	final static int Red = 0;
	final static int Green = 1;
	final static int Blue = 2;
	
	static int[][] Cost;
	static int[][] DP;
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
        
		Cost = new int[N][3];
		DP = new int[N][3];
		
		for(int i = 0; i < N; i++) {
			Cost[i][Red] = in.nextInt();
			Cost[i][Green] = in.nextInt();
			Cost[i][Blue] = in.nextInt();
		}
		
		// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
		DP[0][Red] = Cost[0][Red];
		DP[0][Green] = Cost[0][Green];
		DP[0][Blue] = Cost[0][Blue];
		
		
		System.out.print(Math.min(Paint_cost(N- 1, Red), Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue))));
	}
	
	static int Paint_cost(int N, int color) {
		
		// 만약 탐색하지 않은 배열이라면
		if(DP[N][color] == 0) {
			
			// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
			if(color == Red) {
				DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
			}
			else if(color == Green) {
				DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
			}
			else {
				DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
			}
			
		}
		
		return DP[N][color];
	}
}

 

 

 

동적계획법의 가장 정석적인(?) 방법이라 할 수 있겠다. 참고로 숫자로만 하면 색상이 헷갈릴 수 있을 것 같아 이해하기 쉽도록 Red, Green, Blue 변수를 선언해주었다. 이렇게 해주는게 좀 더 이해하는데 편할 것이다.

 

 

 

---

- 방법 2 : [재귀 + BufferedReader]

 

 

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 각 집에대한 페인팅 비용을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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

public class Main {
	
	final static int Red = 0;
	final static int Green = 1;
	final static int Blue = 2;
	
	static int[][] Cost;
	static int[][] DP;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		Cost = new int[N][3];
		DP = new int[N][3];
		
		StringTokenizer st;
		for(int i = 0; i < N; i++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			
			Cost[i][Red] = Integer.parseInt(st.nextToken());
			Cost[i][Green] = Integer.parseInt(st.nextToken());
			Cost[i][Blue] = Integer.parseInt(st.nextToken());
		}
		
		// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
		DP[0][Red] = Cost[0][Red];
		DP[0][Green] = Cost[0][Green];
		DP[0][Blue] = Cost[0][Blue];
		
		
		System.out.println(Math.min(Paint_cost(N- 1, Red), Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue))));
	}
	
	static int Paint_cost(int N, int color) {
		
		// 만약 탐색하지 않은 배열이라면
		if(DP[N][color] == 0) {
			
			// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
			if(color == Red) {
				DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
			}
			else if(color == Green) {
				DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
			}
			else {
				DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
			}
			
		}
		
		return DP[N][color];
	}
}

 

 

 

만약 알고리즘을 정확하게 이해했다면 크게 어려울 것은 없을 것이다. 

 

 

 

 

 

---

- 방법 3 : [반복문 + BufferedReader]

 

 

 

 

 

반복문으로 풀이하는 방법이다. 어쩌면 이 방법이 더 직관적으로 보일 수 있다.

 

 

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

public class Main {

	final static int Red = 0;
	final static int Green = 1;
	final static int Blue = 2;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());

		int[][] Cost = new int[N][3];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			Cost[i][Red] = Integer.parseInt(st.nextToken());
			Cost[i][Green] = Integer.parseInt(st.nextToken());
			Cost[i][Blue] = Integer.parseInt(st.nextToken());

		}

		// 1부터 N-1까지 각 i별 i-1의 서로 다른 색상 중 최솟값을 누적하여 더한다.  
		for (int i = 1; i < N; i++) {
			Cost[i][Red] += Math.min(Cost[i - 1][Green], Cost[i - 1][Blue]);
			Cost[i][Green] += Math.min(Cost[i - 1][Red], Cost[i - 1][Blue]);
			Cost[i][Blue] += Math.min(Cost[i - 1][Red], Cost[i - 1][Green]);
		}

		System.out.println(Math.min(Math.min(Cost[N - 1][Red], Cost[N - 1][Green]), Cost[N - 1][Blue]));
	}

}

 

 

 

즉, 모든 경우의 수 중 최솟값을 더해나가면서 구하는 방식이다. 이것도 동적계획법이다. 가끔 메모이제이션이 어디에 쓰이는지 모르겠다고 할 수도 있겠다만.. 재귀의 경우 명확하게 함수 호출로 인해 메모이제이션을 활용하면 눈에 확연하게 보이지만 반복문은 작은 문제들을 풀어나가면서 큰 문제로 나아가는 방식이기 때문에 별다른 차이점을 못느꼈을수도 있다.

 

Cost[][] 배열 호출하면서 이전에 풀었던 문제의 값을 그대로 갖고와 활용한다. 이 것 또한 메모이제이션이니 기억해두시길 바란다.

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 21670715  -  방법 3 : 반복문 + BufferedReader

채점 번호 : 21670707  -  방법 2 : 재귀 + BufferedReader

채점 번호 : 21670694  -  방법 1 : 재귀 + Scanner 

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

그리고 알고리즘의 차이는 크게 없는듯..

 

 

---

• 정리

 

 

 

 

아마 대부분 어렵지 않게 이해했을 것이다. (만약 이해되지 않는 부분이 있다면 댓글 남겨주시면 바로 알려주겠습니다!)

다른 분들 풀이 보니 거의 대부분 방법3과 같은 풀이 방식으로 풀었다. 그래도 여러분들이 만약 이 포스팅을 본다면 이왕 본 김에 한 번쯤은 동적계획법에 맞게 조금은 어렵더라도 이해하고 풀이해보시면 좋을 것 같다. 조금 시간이 걸리더라도 알고리즘을 완벽히 이해해야 다음 단계의 알고리즘 문제라던가 여러 코딩테스트에서도 적절하게 이용할 수 있다.