[Baekjoon] 1018_체스판 다시 칠하기

Silver IV

문제(출처: https://www.acmicpc.net/problem/1018)

---

< 체스판 다시 칠하기 >

 

문제 풀이 

 

보드를 8x8 크기의 체스판으로 잘라 'B'로 시작할 때와 'W'로 시작할 때를 각각 계산하여 다시 칠해야 하는 정사각형 개수의 최솟값을 구한다.

 

 my solution (Java)

import java.io.*;
import java.util.*;

public class _1018_ { // 체스판 다시 칠하기

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		char arr[][] = new char[n][m];
		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j);
			}
		}

		char temp[][] = new char[8][8];
		int result = n * m;
		for (int i = 0; i <= n - 8; i++) {
			for (int j = 0; j <= m - 8; j++) {
				for (int x = i; x < i + 8; x++) {
					for (int y = j; y < j + 8; y++) {
						temp[x - i][y - j] = arr[x][y];
					}
				}
				int cnt = 0;
				char c[] = new char[] { 'B', 'W' };
				int idx = 0;

				for (int x = 0; x < 8; x++) {
					if (x % 2 == 0) {
						idx = 0;
					} else {
						idx = 1;
					}
					for (int y = 0; y < 8; y++) {
						if (x % 2 == 0) {
							if (temp[x][y] != c[idx++]) {
								cnt += 1;
							}
							if (idx == 2) {
								idx = 0;
							}
						} else {
							if (temp[x][y] != c[idx--]) {
								cnt += 1;
							}
							if (idx == -1) {
								idx = 1;
							}
						}
					}
				}
				result = Math.min(result, cnt);

				cnt = 0;
				for (int x = 0; x < 8; x++) {
					if (x % 2 == 0) {
						idx = 1;
					} else {
						idx = 0;
					}
					for (int y = 0; y < 8; y++) {
						if (x % 2 == 0) {
							if (temp[x][y] != c[idx--]) {
								cnt += 1;
							}
							if (idx == -1) {
								idx = 1;
							}
						} else {
							if (temp[x][y] != c[idx++]) {
								cnt += 1;
							}
							if (idx == 2) {
								idx = 0;
							}
						}
					}
				}
				result = Math.min(result, cnt);
			}
		}
		System.out.println(result);
	}
}

변수)
n, m : 보드 크기
arr : 보드 값
str : 보드 상태 (행)
temp : 8x8 체스판
result : 다시 칠해야 하는 정사각형 개수 최솟값
cnt : 다시 칠해야 하는 정사각형 개수
c : ['B', 'W']
idx : index

 

보드의 크기를 입력받는다. 보드의 정보를 입력받아 arr에 저장한다. arr를 8x8 크기만큼 잘라 temp 배열에 저장한다. 다시 칠해야 하는 정사각형 개수를 구하기 위해 다음 과정을 수행한다.

 

'B'로 시작하는 경우

1) 행%2가 0일 경우 - idx를 0으로 저장한다.

1-1) c의 idx값과 일치하지 않으면 cnt 값을 1 증가한다.

1-2) idx 값이 범위를 벗어나는 경우 idx를 0으로 저장한다.

2) 행%2가 1일 경우 - idx를 1로 저장한다.

2-1) c의 idx 값과 일치하지 않으면 cnt 값을 1 증가한다.

2-2) idx 값이 범위를 벗어나는 경우 idx를 1로 저장한다.

result 값을 현재 값과 cnt 값 중에서 최솟값으로 저장한다.

 

'W'로 시작하는 경우 

1) 행%2가 0일 경우 - idx를 1로 저장한다.

1-1) c의 idx값과 일치하지 않으면 cnt 값을 1 증가한다.

1-2) idx 값이 범위를 벗어나는 경우 idx를 1로 저장한다.

2) 행%2가 1일 경우 - idx를 0으로 저장한다.

2-1) c의 idx 값과 일치하지 않으면 cnt 값을 1 증가한다.

2-2) idx 값이 범위를 벗어나는 경우 idx를 0으로 저장한다.

result 값을 현재 값과 cnt 값 중에서 최솟값으로 저장한다.

 

최종 result 값을 출력한다.

---

문제를 해결한 후에 풀이 방법을 찾아보니 'B'로 시작하는 경우와 'W'로 시작하는 경우 둘 중에 하나만 구한 후 64에서 그 값을 빼면 다른 하나의 경우 값이 나오는 것을 알 수 있었다. 

 

---