백준 1018번: 체스판 다시 칠하기

문제

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

---

풀이

M x N 크기의 보드를 8 x 8 크기로 잘랐을 때 체스판처럼 만들기 위해 다시 칠해야 하는 칸의 최소 개수를 구하기 위해서 만들 수 있는 모든 8 x 8의 경우의 수를 체크합니다.

---

코드

C언어

모든 경우의 수를 8 x 8 크기로 잘랐을 때 가장 왼쪽 상단에 있는 칸의 색을 기준으로 나머지 칸의 색을 바꾼 개수를 의미하는 cnt와 가장 왼쪽 상단에 있는 칸의 색을 반대되는 색으로 다시 칠한 뒤에 이를 기준으로 나머지 칸의 색을 바꾼 개수를 의미하는 64 - cnt를 구한 뒤에 둘 중 더 작은 수를 최소 개수를 의미하는 min과 비교하며 가장 작은 값을 구합니다.

보드의 색의 변경 여부를 확인하기 위해 조사하는 보드의 각각 x축과 y축을 담당하는 l, k를 포함한 for문에서 현재 위치의 인덱스 값의 홀짝이 같은 경우(2칸씩 이동)는 기준과 같아야 하는 경우, 홀짝이 다른 경우(1칸 이동한 뒤에 2칸씩 이동)는 색이 기준과 달라야 하는 경우로 나눠 비교하는 방식을 사용했습니다.

함수를 사용하지 않아 상대적으로 지저분해 보이는 모습입니다.

#include <stdio.h>
main() {
	char chess[51][51];
	int x, y, min = 64;
	scanf("%d %d", &x, &y);
	for (int i = 0; i < x; i++) {
		scanf("%s", &chess[i]);
	}
	for (int i = 0; i <= x - 8; i++) {
		for (int j = 0; j <= y - 8; j++) {
			int cnt = 0;
			if (chess[i][j] == 'W') {
				for (int k = 0; k < 8; k++) {
					for (int l = 0; l < 8; l++) {
						if (k % 2 != l % 2) {
							if (chess[i + k][j + l] != 'B') {
								cnt++;
							}
						}
						else if (k % 2 == l % 2) {
							if (chess[i + k][j + l] != 'W') {
								cnt++;
							}
						}
					}
				}
			}
			else if (chess[i][j] == 'B') {
				for (int k = 0; k < 8; k++) {
					for (int l = 0; l < 8; l++) {
						if (k % 2 != l % 2) {
							if (chess[i + k][j + l] != 'W') {
								cnt++;
							}
						}
						else if (k % 2 == l % 2) {
							if (chess[i + k][j + l] != 'B') {
								cnt++;
							}
						}
					}
				}
			}
			int tmp = cnt < 64 - cnt ? cnt : 64 - cnt;
			min = min < tmp ? min : tmp;
		}
	}
	printf("%d", min);
}

자바

위와 같은 방법이지만 함수를 사용하여 상대적으로 깔끔해 보이는 모습입니다.

check 함수는 위에서의 cnt와 64 - cnt 중 더 작은 수를 반환하고 main 함수 안에서 최소 개수를 의미하는 min과 비교하며 가장 작은 값을 구합니다.

보드의 색의 변경 여부를 확인하기 위해 함수 내부에서 가장 왼쪽 상단에 있는 칸의 색을 wb에 넣고 1칸씩 이동하면서 wb를 변경해가며 비교하는 방식을 사용했습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static char[][] chess;

    public static int check(int x, int y) {
        int cnt = 0;
        char wb = chess[x][y];
        for (int i = x; i < x + 8; i++) {
            for (int j = y; j < y + 8; j++) {
                if (chess[i][j] != wb) {
                    cnt++;
                }
                if (wb == 'W') {
                    wb = 'B';
                } else wb = 'W';
            }
            if (wb == 'W') {
                wb = 'B';
            } else wb = 'W';
        }
        return Math.min(cnt, 64 - cnt);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        chess = new char[n][m];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                chess[i][j] = str.charAt(j);
            }
        }
        int min = 64;
        for (int i = 0; i <= n - 8; i++) {
            for (int j = 0; j <= m - 8; j++) {
                min = Math.min(min, check(i, j));
            }
        }
        System.out.println(min);
    }
}

 

---

결론

함수의 사용 여부에 따라 깔끔함과 가독성의 정도가 달라지는 것을 직접 체감하게 되었고 가끔은 이런 무식한(?) 방식으로 모든 경우의 수를 전부 조사하는 것이 더 빠르고 확실하다는 것을 알게 되었습니다.