[백준] JAVA - 1018.체스판다시칠하기

생각

처음에 BFS 로 풀려고 했습니다. BFS가 진행될때 같은 depth들은 색깔이 모두 동일해야한다라는 생각을 가지고 구현했지만 계속 답이 안나와서 결국 BFS를 포기하고 B,W색깔이 반복되는 인덱스들의 규칙을 찾아서 문제를 다시 풀었습니다. 사방탐색을 하지 않는 문제인데 굳이 BFS로 접근했습니다. 문제를 보고 계속 어떤문제인지 혼자 판단하고 이 틀에 맞춰서 문제를 푸는 습관을 버리도록 노력해야겠습니다.

 

시작이 B일때와 W일때 무엇이 최소값인지 모르기 때문에 두가지 경우를 모두 체크했습니다.

시작이 W일때 행과 열의 인덱스 합이 짝수일때 B가 칠해져있으면 다시 칠해야 하는 경우입니다. 반대로 행과 열의 합이 홀수일때 W가 칠해져있으면 다시 칠해야 하는 경우입니다. 마찬가지로 시작이 B일때도 동일하게 처리해줍니다.

 

Java code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Chess{
	int y;
	int x;
	public Chess(int y, int x) {
		this.y = y;
		this.x = x;
	}
}

public class Baekjoon_1018_체스판다시칠하기 {
/**
 * N*M 보드에서 8*8크기를 선택했을때 최소로 다시 색칠하는 최소값 구하기
 * 8*8을 어디서부터 시작해야될까? 브루트포스
 * (행,열) 합으로 올바른색깔 판단 가능
 * @throws IOException 
 * 
 * */
	static int R,C;
	static char[][] map;
	
	static boolean[][] visited;
	static char color[] = {'W','B'};
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	static int ans;
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] init = br.readLine().split(" ");
		R = Integer.parseInt(init[0]);
		C = Integer.parseInt(init[1]);
		map = new char[R][C];
		
		visited = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			char[] c = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = c[j];
			}
		}
		ans = Integer.MAX_VALUE;
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				//solve(i,j);
				ans = Math.min(ans, coloring(i, j));
			}
		}
		System.out.println(ans);
	}
	/*
	private static void solve(int i, int j) {
		
		//divide
		int sizeR = i+8;
		int sizeC = j+8;
		if(sizeR > 8 || sizeC > 8) return;
		//solve
		for (boolean[] row : visited) {
			Arrays.fill(row, false);
		}	
		
		int idx=0;
		for (int k = 0; k < color.length; k++) {
			if (color[k] == map[i][j]) {
				idx = k;
			}
		}
		
		int cnt = 0;
		Queue<Chess> q = new LinkedList<Chess>();
		visited[i][j] = true;
		q.add(new Chess(i, j));
		
		while(!q.isEmpty()) {
			int depthSize = q.size();//같은 depth끼리는 색이 모두 동일
			idx = (idx+1) % 2; //depth 색깔 인덱스
			for (int k = 0; k < depthSize; k++) {
				Chess now = q.poll();
//				if(color[idx] != map[now.y][now.x]) {
//					cnt++;
//				}
				for (int d = 0; d < 4; d++) {
					int ny = now.y + dy[d];
					int nx = now.x + dx[d];
					if(ny < i || ny >= sizeR || nx < j || nx >= sizeC) {
						continue;
					}
					if(!visited[ny][nx]) {
						if(color[idx] != map[ny][nx]) {
							cnt++;
						}
						visited[ny][nx] = true;
						q.add(new Chess(ny, nx));
					}
				}
			}
		}
		ans = ans < cnt ? ans : cnt;
	}
	*/
	
	private static int coloring(int y, int x) {
		if(y+8 > R || x + 8 > C) return Integer.MAX_VALUE;
		int whiteCnt = 0;
		int blackCnt = 0;

		//시작이 W일때
		for (int i = y; i < y+8; i++) {
			for (int j = x; j < x+8; j++) {
				if((i+j) % 2 == 0 ) { //행 열 합이 짝
					if(map[i][j] != 'W') {
						whiteCnt++;
					}
				}
				if((i+j) % 2 == 1){// 행 열 합이 홀
					if(map[i][j] != 'B') {
						whiteCnt++;
					}
				}
				
				
			}
		}
		//시작이 B일때
		for (int i = y; i < y+8; i++) {
			for (int j = x; j < x+8; j++) {
				if((i+j) % 2 == 0 ) { //행 열 합이 짝
					if(map[i][j] != 'B') {
						blackCnt++;
					}
				}
				if((i+j) % 2 == 1){// 행 열 합이 홀
					if(map[i][j] != 'W') {
						blackCnt++;
					}
				}
				
				
			}
		}
		return Math.min(blackCnt, whiteCnt);
	}

}