[Java] 백준알고리즘 #1018 체스판 다시 칠하기

백준알고리즘 #1018 체스판 다시 칠하기 문제

임의의 n x m 크기의 보드를 8 x 8 의 보드로 잘라내어 체스판을 만들기 위해 색상을 다시 칠하는 문제이다.

조금 단순하지만 무식한 방식으로 풀어보았다.

 

먼저 비교할 두 체스판 (흰색이 먼저 오는 체스판 과 검은색이 먼저 오는 체스판) 을 만들어둔다.

char[][] b = new char[8][8];
char[][] w = new char[8][8];
for (int i = 0; i < 8; i++) {
	for (int j = 0; j < 8; j++) {
		if ((i + j) % 2 == 0) {
			b[i][j] = 'B';
			w[i][j] = 'W';
		} else {
			b[i][j] = 'W';
			w[i][j] = 'B';
		}
	}
}

 

그리고 n x m 크기의 보드를 이차원 배열에 입력받는다.

int n = sc.nextInt();
int m = sc.nextInt();
char[][] a = new char[n][m];
for (int i = 0; i < n; i++) {
	String tmp = sc.next();
	for (int j = 0; j < m; j++) {
		a[i][j] = tmp.charAt(j);
	}
}

자바에서 Scanner를 통해 입력을 받을 때에 char형은 입력받을 수 없다. 

따라서 임시변수 String tmp 를 만들어 둔 후 charAt()함수를 이용해 하나씩 분리하여 배열에 저장하였다.

 

이후 흰색이 먼저 오는 체스판 1과, 검은색이 먼저 오는 체스판 2를 각각 비교하기 위해 count변수를 2개 만든다.

틀린 갯수를 확인하기 위한 err변수도 만들어 준다. 이때 err는 64로 초기화 하고 (8 x 8 크기의 체스판이기 때문)

이후 틀린 갯수가 err보다 작다면 err에 틀린 갯수를 넣어 주면 될 것이다.

int count1, count2, err;
err = 64;

 

이제 만들어둔 체스판 1, 2와 입력받은 n x m 크기의 보드를 비교 해 볼텐데 나는 굉장히 단순한 방법으로 하나씩 비교해 보는 방법을 써 보았다.

for (int i = 0; i < n - 7; i++) {
	for (int j = 0; j < m - 7; j++) {
		count1 = 0;
		count2 = 0;
		for (int k = 0; k < 8; k++) {
			for (int l = 0; l < 8; l++) {
				if (a[i + k][j + l] != b[k][l]) {
					count1++; 
				}
				if (a[i + k][j + l] != w[k][l]) {
					count2++; 
				}

			}
		}
		if (err > count1) {
			err = count1;
		}
		if (err > count2) {
			err = count2;
		}
	
	}

}

무려 4중 for문을 이용했는데 

첫번째와 두번째 for문은 전체 보드에서 잘라내는 범위를 지정할 for문이고

세번째와 네번째 for문은 잘라낸 범위와 미리 만들어둔 체스판 1, 2를 비교하는 for문이라 보면 되겠다.

 

전체 보드를 8칸으로 잘라내야 하므로

1	2	3	4	5	6	7	8	9	10
2
3
4
5
6
7
8
9

위와 같은 판이 있을 때

가로의 경우 1~8 / 2~9 / 3~10 와 같이 8칸씩 3번 잘라내야 하고

세로의 경우 1~8 / 2~9 까지 2번 잘라내야 한다

따라서 이 범위는 i가 0부터 n - 8이 아닌 n - 7 까지가 된다 ( 범위를 < 가 아닌 <=로 지정한다면 n - 8 로 해도 된다.)

 

가로 세로의 범위를 각각 지정해주고 count1, 2 변수를 초기화 해 준 후 배열의 각 원소를 체스판 1, 2와 각각 비교해준다.

만약 틀린 부분이 있다면 이 count를 증가시킨 후 세번째와 네번째 for문이 완료된 후 ( 잘라낸 판의 비교가 끝난 후)

count1, 2 와 err을 비교하여 작은 수를 err에 저장시킨다. 

이 과정이 끝나고 나면 err에는 결국 가장 작은 err 수, 즉 다시 칠해야 하는 정사각형의 수가 남아있게 된다.

 

전체 코드를 보면 다음과 같다.

import java.util.Scanner;

public class Back1018 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		char[][] b = new char[8][8];
		char[][] w = new char[8][8];
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				if ((i + j) % 2 == 0) {
					b[i][j] = 'B';
					w[i][j] = 'W';
				} else {
					b[i][j] = 'W';
					w[i][j] = 'B';
				}
			}
		}
		char[][] a = new char[n][m];
		for (int i = 0; i < n; i++) {
			String tmp = sc.next();
			for (int j = 0; j < m; j++) {
				a[i][j] = tmp.charAt(j);
			}
		}
		int count1, count2, err;
		err = 64;
		for (int i = 0; i <= n - 8; i++) {
			for (int j = 0; j <= m - 8; j++) {
				count1 = 0;
				count2 = 0;
				for (int k = 0; k < 8; k++) {
					for (int l = 0; l < 8; l++) {
						if (a[i + k][j + l] != b[k][l]) {
							count1++; 
						}
						if (a[i + k][j + l] != w[k][l]) {
							count2++; 
						}

					}
				}
				if (err > count1) {
					err = count1;
				}
				if (err > count2) {
					err = count2;
				}

			}

		}
		System.out.println(err);

	}

}

 

위 과정은 매우 단순하고 무식한 방법으로 풀이한 것이므로 코드가 굉장히 복잡해진다.

더 쉬운 방법도 물론 있겠지만 내가 생각한 방법은 이게 최선이었다..