[JAVA] [SWEA] 4613. 러시아 국기 같은 깃발

2016년은 삼성전자가 러시아 현지법인을 설립한지 20주년이 된 해이다. 이를 기념해서 당신은 러시아 국기를 만들기로 했다.

먼저 창고에서 오래된 깃발을 꺼내왔다. 이 깃발은 N행 M열로 나뉘어 있고, 각 칸은 흰색, 파란색, 빨간색 중 하나로 칠해져 있다.

당신은 몇 개의 칸에 있는 색을 다시 칠해서 이 깃발을 러시아 국기처럼 만들려고 한다. 다음의 조건을 만족해야 한다.

• 위에서 몇 줄(한 줄 이상)은 모두 흰색으로 칠해져 있어야 한다.

• 다음 몇 줄(한 줄 이상)은 모두 파란색으로 칠해져 있어야 한다.

• 나머지 줄(한 줄 이상)은 모두 빨간색으로 칠해져 있어야 한다.

이렇게 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여라.

     

     

첫 번째 예제이다. 왼쪽에 있는 그림이 입력이다. 중간에 있는 그림에 X가 적힌 칸들을 새롭게 색칠하여 오른쪽에 있는 그림과 같은 깃발을 만들면 최적이다.

 

이 문제의 경우 내가 알기로 완탐만 잘 돌리더라도 가능한 문제로 알고 있다.

 

하지만 더 효율적으로 풀기위해 백트래킹을 넣어 DFS 를 시도하여 해결하였다.

 

먼저 문제에서 내가 생각한 키 포인트는 맨 윗줄은 흰색 맨 밑줄은 빨간색으로 칠해놓고 시작해야한다는 점이고

 

순서만 생각하면 그 뒤로 문제를 해결할 수 있다.

 

따라서 흰빨파빨 같이 빨간색이 파란색보다 먼저 나온다던가 흰흰빨빨 과 같이 파란색이 나오지 않는 경우를 없게

 

하여 문제를 풀어주면 된다.

 

결론적으로 이 줄에 무슨 색이 들어갈 것인지를 규칙에 맞게 설정 해준 뒤 색을 칠했을때 새로칠해야하는 칸 수를 세고

 

그중에서 최소값을 출력하면 되는 문제이다.

 

전체 코드는 다음과 같다. 총 테스트 케이스가 5개 이기때문에 메모리 적인 부분은 생각할 필요가 없어 그냥 작성해 주었다.

 

그리고 테스트 케이스가 많거나 DFS 가 많이 진행되어 static한 field를 많이 참조하게 된다면 시간이 많이 걸릴 수

 

있으니 DFS가 많이 진행되는 경우라면 메소드의 인자값으로 되도록 넣어주도록 하자

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Solution {
	static int N;
	static int M;
	static String[][] flag;
	static int cnt;
	static int min;
	static int count;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		String[] s = null;
		for(int t=1; t<=T; t++) {
			s = br.readLine().split(" ");
			N = Integer.parseInt(s[0]);
			M = Integer.parseInt(s[1]);
			flag = new String[N][M];
			cnt = 0;
			min = Integer.MAX_VALUE;
			for(int i=0; i<N; i++) {
				flag[i] = br.readLine().split("");
			}
			for(int i=0; i<M; i++) {
				if(!flag[0][i].equals("W")) cnt++;
				if(!flag[N-1][i].equals("R")) cnt++;
			}
			dfs(0, new String[N-2], 0, 0);
			bw.write("#"+t+" "+(cnt+min)+"\n");
		}
		br.close();
		bw.close();
	}
	
	static void dfs(int depth, String[] arr, int blue, int red) {
		if(depth == N-2) {
			if(blue == 0) return;
			count = 0;
			for(int i=0; i<arr.length; i++) {
				for(int j=0; j<M; j++) {
					if(!flag[i+1][j].equals(arr[i])) count++;
				}
			}
			if(count < min) {
				min = count;
			}
			return;
		}
		if(blue == 0 && depth != N-1 && red == 0) {
			arr[depth] = "W";
			dfs(depth+1, arr, blue, red);
		}
		
		if(red == 0) {
			arr[depth] = "B";
			dfs(depth+1, arr, blue+1, red);
		}
		
		
		arr[depth] = "R";
		dfs(depth+1, arr, blue, red+1);
	}

}