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

 

링크

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

1018번: 체스판 다시 칠하기

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

접근방법

인접하는 배열이 상반된 문자를 갖도록 바꾸고 그 숫자를 반환된 값이 최소인 부분을 찾는 문제다. N * M의 가변 크기의 보드이지만, 잘라서 분석할 부분은 고정(8*8) 크기이다. 문제를 조금 더 쪼개서 쉽게 생각해보자. 문제는 크게 1) 쪼개는 부분과 2)칠하는 부분으로 나누어질 수 있다.

• 일단 칠할 체스판을 나누는 법부터 생각해보면, 8 * 8 크기가 되는 부분은 모두 사용할 수 있다. 1) 따라서, N * M에서 8 * 8 크기가 나오는 부분은 전부 쪼개는 부분이 필요하다.  
• 8 * 8크기 안에서 체스판을 칠해야 하는 경우를 구해야 한다. 인접 블록이 서로 다른 문자를 가지고 있어야 하므로, 2) 블록을 비교하여 색이 같다면 바꾸어주는 부분이 필요하다.

이 부분에 중심을 두고 코딩을 시작했고, 크게 두번 정도 구현에 실패했다.

 

실패 원인

 1. 입력을 그대로 받아 쓰고 싶어 String 형태의 ArrayList를 사용했다.

ArrayList를 사용하면, 가변적인 크기를 이용할 수 있으니 편하겠다 판단하고 구현하였다. 문제는 ArrayList가 아닌 string이었다. 인접 배열의 같은 색을 바꾸기 위해 결국 문자열을 쪼개고 변경한 뒤 다시 합쳐야 하는 과정을 거쳐야 한다. 그러나  replace 메서드를 이용하다 보니, 문자가 중복되어 방법을 바꿔야 했다. substring을 이용하자니, 결국 인덱스를 알아야 하고 코드는 23인치 내화면을 벗어나려 했다. 처음부터 charactor로 접근했다면, 코드가 길지도 접근도 쉬웠을 것이다.

 

 2. 배열 지식의 구멍

 배열은 참조형 객체이다. 그 말은 대충 복사하면, 얕은 복사가 일어난다는 것이다. 얕은 복사로 인해 원본 데이터가 유지되지 않아 정확한 결과값이 나오지 않았다. 기본형과 참조형에 대한 포스팅링크 걸어둔다. 이해가 필요하다면, 참고하자. 

 

https://j-sik.tistory.com/9 

[JAVA] 자료형 - 기본형(Primitive type)과 참조형(Reference type)

 

 

코드

 

import java.util.Scanner;

public class BJ_1018 {
    char[][] data;


    public static void main(String[] args) {

        BJ_1018 test = new BJ_1018();
    }

    public BJ_1018() {
        Scanner scanner = new Scanner(System.in);
        int depth = scanner.nextInt(); // 세로
        int width = scanner.nextInt(); // 가로
        data = new char[depth][width];

        scanner.nextLine();
        for (int i = 0; i < depth; i++) {
            String str = scanner.nextLine();
            for (int j = 0; j < width; j++) {
                data[i][j] = str.charAt(j);
            }
        }


        solution(depth,width);

    }

    public int solution(int depth, int width) {
        int answer = 3000;
	//1) 8 * 8 블록을 쪼개는 과정
        for (int i = 0; i < depth; i++) {
            for (int j = 0; j < width; j++) {

                if (chessArea(i, j, depth, width)) {

                    answer=Math.min(answer,Math.min(changeCount(data,i,j,0),changeCount(data,i,j,1)));
                }

            }
        }

        System.out.println(answer);
        return answer;
    }

    //8*8 크기 판단
    public boolean chessArea(int y, int x, int depth, int width) {
        if (y + 7 < depth && x + 7 < width) {
            return true;
        }
        return false;
    }
	//B W Swapping
    public char swapChar(char ch) {
        if (ch == 'B') {
            return 'W';
        }
        return 'B';
    }
    
	//2) 체스판화 시키고 칠한 수를 세는 메소드
    public int changeCount(char[][] data, int y, int x, int opt) {
        char[][] tmp = new char[data.length][data[0].length];
        int answer = 3000;
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[0].length; j++) {
                tmp[i][j] = data[i][j];
            }
        }

        int count = 0;

        if (opt == 1) {
            tmp[y][x] = swapChar(tmp[y][x]);
            count++;
        }

        for (int i = y; i < y + 8; i++) {

            //처음 시작만 비교안함
            //나머지에 대해서는 윗줄 첫 문자와 비교
            if( i != y){
                if(tmp[i-1][x] == tmp[i][x]){
                    tmp[i][x]= swapChar(tmp[i][x]);
                    count++;
                }
            }

            for (int j = x+1; j < x + 8; j++) {
                if(tmp[i][j-1] == tmp[i][j]){
                    tmp[i][j] = swapChar(tmp[i][j]);
                    count++;
                }
            }
        }

        return count;
    }

}