백준)1018.체스판 다시 칠하기 - 풀이 및 반례(JAVA)

작년 8월 같은 문제를 풀고 포스팅 한 적이 있다.

마음 같아선 작년의 모든 포스팅을 삭제하고 싶지만, 내 블로그의 취지인 '성장의 기록'을 위배하는 듯 하여 남겨둔다ㅎㅎ 

 

작년 같은 문제 포스팅(별로 도움 안됩니다)

dreamingdreamer.tistory.com/73?category=797039

백준)Q.1018_체스판 다시 칠하기(완전탐색(Brute-fore Search))

 

 

작년의 코드와 크게 다른 점은, 일단 이 문제는 진짜로 무식하게 체스판을 자를 필요가 없다는 거다. 

(작년의 나는 cut이라는 메서드까지 친히 만들어 두고 사용했었다. 왜그랬을까ㅡ,ㅡ?)

그저 색깔이 같아야 하는 위치에 같은 색깔이 있는지만 비교해주면 됐다.

 

 

1. 알고리즘  

 1) 2중for문으로 입력받은 체스판을 돌며 8*8칸을 만들 수 있는지 확인한다. 예를들면 입력받은 값이 10*10라면, i가 2이하일 때, j가 2이하일 때만 고려해주면 된다.  

 

 2) 검색 대상인 8*8체스판에서 [0,0]과 색깔이 같아야 하는 경우를 확인한다.(여기서 말하는 [0,0]은 입력받은 배열을 의미하는 것이 아닌 잘려진 체스판에서의 좌표를 의미한다)

아래 표를 확인하면, [0,0]과 색깔이 같아야 하는 좌표는 x+y가 짝수인 경우이다.

따라서 x좌표+y좌표가 짝수일때는 0,0과 색깔이 같아야 하는데, 같지 않다면 카운팅을 하고, x좌표+y좌표가 홀수일때는 0,0과 색깔이 달라야 하는데, 같다면 카운팅을 하면 된다. 

 

3) 고려해야 할 게 있다면 아래와 같은 경우이다. 

 

8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

 

위의 예시에서 [0,0]의 색깔을 기준으로 비교해버린다면 63을 리턴해버린다. 

[0,0]의 색만 바꾸면 되는데, [0,0]을 기준으로 잡아버리니 그렇다.  

이건 어떻게 해결 하면 될까? 

 

첫번째로 나는 아래와 같이 해결했었다. 

// x - 세로위치, y - 가로위치
    public static int switchEachColor(int x, int y) {

        int finalCount = 64;
        char[] blackNWithe = {'B', 'W'};

        for (int k = 0; k < 2; k++) {
            char firstChar = blackNWithe[k];
            int count = 0;
            Loop:
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    /* if((i + j) % 2 == 0) {
                        // 색깔이 같아야 하는 경우
                        if(inputBoard[i + x][j + y] != firstChar) {
                            count++;
                        }
                    } else {
                        // 색깔이 달라야 하는 경우
                        if(inputBoard[i + x][j + y] == firstChar) {
                            count++;
                        }
                    }*/
                    count = ((i + j) % 2 == 0) ? ((inputBoard[i + x][j + y] != firstChar) ? count + 1 : count)
                            : ((inputBoard[i + x][j + y] == firstChar) ? count + 1 : count);
                    if (result <= count || finalCount <= count) {
                        break Loop;
                    }
                }
            }
            finalCount = count < finalCount ? count : finalCount;
        }
        return finalCount;
    }

count = (( i+j.... 부분이 너무 가독성이 떨어지는 듯 하여 주석으로 if-else문을 작성했다. 

그냥 [0,0]의 색깔이 B인경우와 W인경우 모두를 확인한 것이다.

그리고 루프 중간에 브레이크 포인트를 심어두었다. 이전 카운트보다 커지는 순간 루프를 멈추는 것이다.

백준에서는 결과적으로 위 코드의 효율성이 더 좋게 나오기는 했다(왜일까...) 

 

두번째 해결법이다. 

    public static int switchEachColor(int x, int y) {
        char firstChar = inputBoard[x][y];
        int count = 0;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if((i + j) % 2 == 0) {
                    // 색깔이 같아야 하는 경우
                    if(inputBoard[i + x][j + y] != firstChar) {
                        count++;
                    }
                } else {
                    // 색깔이 달라야 하는 경우
                    if(inputBoard[i + x][j + y] == firstChar) {
                        count++;
                    }
                }
            }
        }
        count = Math.min(count, 64-count);
        return count;
    }

[0,0]의 색을 기준으로 한다. 그리고 count = Math.min(count, 64-count) 로 반대의 경우를([0,0]이 기준색깔이 되는 것이 아닌, [0,0]의 색깔을 바꿈으로써 바뀌는 count수) 확인했다. (이건 백준의 다른사람 코드를 참고하긴 했다) 

위의 예시에서 63을 리턴하지만, 위와 같이 한다면 1을 리턴하게 되는 것이다. 

 

해결법1(채점번호 ~5821)과 해결법2(채점번호 ~7993)의 결과이다.

 

 

 

2. 나의 코드 

package Brute_force_Search;

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

/*
 * Date : 20. 10. 16
 * Question.No : 백준 1018 - 체스판 다시 칠하기
 * Remark : switchEachColor()에서 중간에 끊어주는 로직(최종 result보다 클경우) 없이 모두 수행. 이후 count와 64-count를 비교하여 작은값을 리턴.
 *          1018_2에 비해 시간이 아주조금 더 걸림.(92)
 */
public class Boj1018 {

    private static char[][] inputBoard = null;
    private static int result = 64;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // [0] - 세로 / [1] - 가로
        String[] size = br.readLine().split(" ");
        inputBoard = new char[Integer.parseInt(size[0])][Integer.parseInt(size[1])];

        for (int i = 0; i < inputBoard.length; i++) {
            String eachLine = br.readLine();
            for (int j = 0; j < inputBoard[i].length; j++) {
                inputBoard[i][j] = eachLine.charAt(j);
            }
        }

        for (int i = 0; i < inputBoard.length; i++) {
            if (!(inputBoard.length - i < 8)) {
                for (int j = 0; j < inputBoard[i].length; j++) {
                    if (!(inputBoard[i].length - j < 8)) {
                        int tmpMin = switchEachColor(i, j);
                        result = tmpMin < result ? tmpMin : result;
                    }
                }
            }
        }
        System.out.println(result);
    }

    public static int switchEachColor(int x, int y) {
        char firstChar = inputBoard[x][y];
        int count = 0;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if((i + j) % 2 == 0) {
                    // 색깔이 같아야 하는 경우
                    if(inputBoard[i + x][j + y] != firstChar) {
                        count++;
                    }
                } else {
                    // 색깔이 달라야 하는 경우
                    if(inputBoard[i + x][j + y] == firstChar) {
                        count++;
                    }
                }
            }
        }
        count = Math.min(count, 64-count);
        return count;
    }


}

 

 

3. 반례 

 

8 
BBWBWBWB 
BWBWBWBW 
WBWBWBWB 
BWBWBWBW 
WBWBWBWB 
BWBWBWBW 
WBWBWBWB 
BWBWBWBW

답 : 1

 

10 10
WWBBWWWBBW
WBBWBWWWWB
WBWBWWBBWW
WBBBBBBBWW
WBBWWWBWWW
WBBBBBWWBB
WWBWWBWWBB
BWWBBWWWBB
BBWBBBBBWB
WWWBBBWWWB

답 : 29

 

8 16
BBBBBBBBBWBWBWBW
BBBBBBBBWBWBWBWB
BBBBBBBBBWBWBWBW
BBBBBBBBWBWBWBWB
BBBBBBBBBWBWBWBW
BBBBBBBBWBWBWBWB
BBBBBBBBBWBWBWBW
BBBBBBBBWBWBWBWB

답 : 0 

 

8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

답 : 2

 

8 8
WWWWWWWB
WBBBBBBB
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

답 : 8