[문제] 백준 1018번 체스판 다시 칠하기

* 출처 www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

내 풀이

 

5번 틀린 후 드디어 맞춘 문제다. 

얼핏보면 쉬워보이는데, 실수할 만한 부분이 나한테는 많았다.

간과했던 부분은, 매트릭스에서 비교할 대상을 어느 부분에 잡느냐에 따라 영역의 색이 달라진다는 것이다.

count함수에서 초기에 비교 대상을 (x,y)로만 잡고 진행해서 틀렸었다.

그래서 시작점을 해당 매트릭스 내의 모든 점으로 두었다.

 

임의의 좌표 (i,j)에 대해, 

1. 짝수행, 짝수열 -> 시작점과 동일

2. 짝수행, 홀수열 -> 시작점과 반대

3. 홀수행, 짝수열 -> 시작점과 반대

4. 홀수행 ,홀수열 -> 시작점과 동일

 

4개의 경우로 나눠서 시작점에 따라 바꿔야할 색의 수를 계산했다.

public class BOJ_1018 {
	static int N;
	static int M;
	static int[][] board;

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

		String[] s = in.readLine().split(" ");
		N = Integer.parseInt(s[0]);	// 행
		M = Integer.parseInt(s[1]);	// 열
		
        //init board
		board = new int[N][M];
		for (int i = 0; i < N; i++) {
			String str = in.readLine();
			for (int j = 0; j < M; j++) {
				char c = str.charAt(j);
				board[i][j] = (c == 'B' ? 0 : 1);	// B면 0, W면 1
			}
		}
		
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (canMakeRect(i, j)) {	//(i,j)에서 8*8 배열을 만들 수 있는지 확인
					int res = count(i, j);	
					min = Math.min(min, res);	// 최소값 갱신
				}
			}
		}
		System.out.println(min);
	}

	// (x,y)에서 8*8 정사각형을 만들 수 있는지 알 수 있는 함수
	static boolean canMakeRect(int x, int y) {
		if (x + 8 <= N && y + 8 <= M) {
			return true;
		}
		return false;
	}
// (x,y)에서 시작하는 보드 - 얼마나 색칠해야 하는지 알 수 있는 함수
	static int count(int x, int y) {
		int min = Integer.MAX_VALUE;
		
		for(int a=x;a<x+8;a++) {
			for(int b =y;b<y+8;b++) {
				int start = board[a][b];	// 시작점에 따라 칠해지는 색이 다르다
				int cntS = 0;
				for (int i = x; i < x+8; i++) {
					for (int j = y; j < y+8; j++) {
						if (i % 2 == 0) {
							if (j % 2 == 0) {
								if (board[i][j] != start) {
									cntS++;
								}
							} else {
								if ((board[i][j] ^ start) != 1){
									cntS++;
								}
							}
						} 
						else {
							if (j % 2 == 0) {
								if ((board[i][j] ^ start) != 1){
									cntS++;
								}
							} else {
								if (board[i][j] != start){
									cntS++;
								}
							}
						}
					}
				}
				min = Math.min(cntS, min);
			}
		}
		
		return min;
	}
}

 

다른 풀이

 

애초에 8*8 배열에 칠할 수 없는 방법은 두가지 방법밖에 없다. 

(처음이 W로 시작할 때랑, B로 시작할 때 2가지)

이를 배열과 비교해보면 된다.