백준 1018 - 체스판 다시 칠하기 (브루트포스)

해당 문제를 한시간안에 풀고 다른 작업을 해야지란 생각을 했던 7시간 전에 나에게 늦었지만 위로를 보내며 글을 쓴다. 

확실히 난 천재는 아닌것 같다. 그렇지만 끈질기긴하지.

각설하고, 이 문제를 해결하면서 겪었던 사항들은 다음과 같다.

 

1. Scanner 데이터형 변수 재 초기화시 런타임에러

2. 이중배열의 복사시에 원했던 깊은복사가 아니라 얕은 복사가 된 문제

3. 직접 짠 로직에서 처리 하지 못한 예외사항 2가지

4. 근본적으로 해당 문제를 해결 할 수 없는 구조였던 나의 코드의 총체적 문제

 

그렇다. 4번을 애초에 1시간이 지났을때만 알았더라도 나머지 6시간은 유용하게 쓰였겠지. 

 

1번 문제

일단 내가 나름짠 코드를 백준에 제출하니

런타임에러가 나왔다. 코드상 에러도 없고 에러가 나올만한 없는데 나왔길래 이번 코드를 짜며

평사시와 달리 Scanner를 두번 초기화 한것을 의심하였다. 결국 그 이유가 맞았다.

입력데이터가 "숫자(공백)숫자(엔터)" 이후에 한줄씩 읽어야 하는 방식이길래

int m = sc.nextInt();
int n = sc.nextInt();

로 m,n을 읽고 다음 데이터들을 바로 for문을 돌려 sc.nextLine()로 한라인 한라인을 읽으면 버퍼에 엔터가 남아있으므로 당연히 문제가 생길거라 생각하고,

sc = new Scanner(System.in);

이렇게 한번 더 초기화를 하고 sc.nextLine()을 사용하여 한라인 한라인 읽으려 했더니 채점시 런타임 에러가 났다.

그래서 입력버퍼를 지우는 방법을 찾아보니

sc.nextLine();

이 한줄을 그냥 넣어주면 버퍼가 지워지더라.

 

 

해결책 :  Scanner의 입력버퍼를 지우고 싶을땐 sc.nextLine(); 한줄 추가. (당연히 해당 함수가 반환하는 데이터는 특정 변수에 대입할 필요 X)

 

 

2번 문제

 

일단 개념을 정의하자.

 

깊은 복사 : 배열을 아주 딥하게 모든것을 다 복사 해버리므로 복사원본배열과 복사된배열은 전혀 다른 배열이 된다.

(원본 데이터 수정시 복사된 배열에 영향 없음)

 

얕은 복사 : 배열을 얕게 그럴싸하게 베껴 온다고 생각하자. 그럴싸하게 베껴왔지만 결국 원본을 따라한것이라 결국 원본과 복사본은 같은것이다.

(원본 데이터 수정시 복사된 배열도 수정됨)

 

배열 복사 방법을 여러가지가 있다.

그 중 배열명.clone() 을 사용하였는데 해당 방법은 이중배열을 대상으로 할때 깊은 복사가 되지 않는다..

 

해결책 :

1. 그냥 이중 for문으로 하나하나 값 대입하기

2. System.arraycopy 사용

 

3번 문제

-1번 예외사항

내 로직은 0,0 부터 시작하고 0,0은 무조건 맞다는 가정하에 위,아래,좌,우를 체크하여 틀린것을 고쳐주는 방식이였다.

해당 로직으로는 

BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBW

위와 같은 경우 내 로직으로는 33번의 수정이 필요했다. (전체 B의 경우 32번이다)

전체의 갯수가 64이기 때문에 최대 바꿔야할 경우 32(반)이라고 생각했는데 33이길래 의아했다..

왜 33이 나오느냐면 B가 맞다는 가정으로 시작하기에 하나하나 다 수정한 뒤 맨 마지막 7,7 위치에 W를 또 B로 바꿔줘야 하기 때문에 말이다.

 

-2번 예외사항

WWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

위와 같은 경우 0,0만 B로 바꿔주면 되는데 W가 맞다는 가정으로 시작하는 내 로직때문에 0,0빼고 모두 바꿔줘야 하므로 64개중 63개의 수정이 필요한 결과가 나왔다.

 

4번 문제

1번의 예외사항만 있다 생각하고 

심플하게 

if(wrongPoint == 33)
    wrongPoint = 31;

이렇게 끝내버릴려고 했으나 

2번째 예외사항을 보고 아~ 구조가 아예 썩었구나란 생각이 들어 결국 다른 해답을 2초만 훑어보고 구조를 다시 짜서 해결하였다.

막상 구조를 바꾸는데는 단 몇분이 걸렸지.

 

결론 :

확신할 수 없는 (모든 예외사항을 염두할 수 없는) 가정을 두고 로직을 짤때는 해당 가정이 틀렸을 경우의 상황에서도 내 로직이 맞는지 생각해볼것.

(EX: 0,0은 무조건 맞다라는 가정으로 로직을 짯다.

0,0만 틀릴 경우에 내 로직이 맞는지 생각해볼것)

 

• 기존 틀린 로직

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();
        char [][] board = new char[m][n];
        int minWrongPt = m * n;
        sc = new Scanner(System.in);

        for(int i = 0; i < m; i++)
        {
            String row = sc.nextLine();
            for(int j = 0; j < n; j++)
            {
                char ch = row.charAt(j);
                board[i][j] = ch;
            }
        }



        for(int r = 0; r <= m-8; r++)
        {
            for(int c = 0; c <= n-8; c++)
            {
                //탐색 시작
                int exploRLimit = r + 8;
                int exploCLimit = c + 8;
                int wrongPoint = 0;
                char [][] cloneBoard = arrCopy(board);

                for(int exRow = r; exRow < exploRLimit; exRow++)
                {
                    for(int exCol = c; exCol < exploCLimit; exCol++)
                    {
                        int up = exRow - 1;
                        int down = exRow + 1;
                        int left = exCol - 1;
                        int right = exCol + 1;
                        char istCh = cloneBoard[exRow][exCol] == 'W' ? 'B' : 'W';

                        if(up >= r)
                        {
                            if(cloneBoard[exRow][exCol] == cloneBoard[up][exCol])
                            {
                                cloneBoard[up][exCol] = istCh;
                                wrongPoint++;
                            }
                        }
                        if(down < exploRLimit)
                        {
                            if(cloneBoard[exRow][exCol] == cloneBoard[down][exCol])
                            {
                                cloneBoard[down][exCol] = istCh;
                                wrongPoint++;
                            }
                        }
                        if(left >= c)
                        {
                            if(cloneBoard[exRow][exCol] == cloneBoard[exRow][left])
                            {
                                cloneBoard[exRow][left] = istCh;
                                wrongPoint++;
                            }
                        }
                        if(right < exploCLimit)
                        {
                            if(cloneBoard[exRow][exCol] == cloneBoard[exRow][right])
                            {
                                cloneBoard[exRow][right] = istCh;
                                wrongPoint++;
                            }
                        }
                    }
                }

                //예외사항
                if(wrongPoint == 33)
                    wrongPoint = 31;

                if(minWrongPt > wrongPoint)
                    minWrongPt = wrongPoint;


            }
        }

        System.out.println(minWrongPt);
    }


    public static char[][] arrCopy(char[][] src)
    {
        char[][] dest = new char[src.length][src[0].length];

        for(int i = 0; i < src.length; i++)
        {
            System.arraycopy(src[i], 0, dest[i], 0, src[0].length);
        }

        return dest;
    }

}

 

• 제출한 정답 로직

import java.util.*;

public class Main{
    public static void main(String[] args) {

        char[][] correctBoard0 = new char[][]
                {{'W','B','W','B','W','B','W','B'},
                 {'B','W','B','W','B','W','B','W'},
                 {'W','B','W','B','W','B','W','B'},
                 {'B','W','B','W','B','W','B','W'},
                 {'W','B','W','B','W','B','W','B'},
                 {'B','W','B','W','B','W','B','W'},
                 {'W','B','W','B','W','B','W','B'},
                 {'B','W','B','W','B','W','B','W'}
                };
        char[][] correctBoard1 = new char[][]
                {{'B','W','B','W','B','W','B','W'},
                 {'W','B','W','B','W','B','W','B'},
                 {'B','W','B','W','B','W','B','W'},
                 {'W','B','W','B','W','B','W','B'},
                 {'B','W','B','W','B','W','B','W'},
                 {'W','B','W','B','W','B','W','B'},
                 {'B','W','B','W','B','W','B','W'},
                 {'W','B','W','B','W','B','W','B'}
                };

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();
        char [][] board = new char[m][n];
        int minWrongPt = m * n;
        sc.nextLine(); //버퍼 지우기

        for(int i = 0; i < m; i++)
        {
            String row = sc.nextLine();
            for(int j = 0; j < n; j++)
            {
                char ch = row.charAt(j);
                board[i][j] = ch;
            }
        }



        for(int r = 0; r <= m-8; r++)
        {
            for(int c = 0; c <= n-8; c++)
            {
                //탐색 시작
                int exploRLimit = r + 8;
                int exploCLimit = c + 8;
                int[] wrongPoint = new int[2];
                int correctBoardRow = 0;
                int correctBoardCol = 0;

                for(int exRow = r; exRow < exploRLimit; exRow++)
                {
                    for(int exCol = c; exCol < exploCLimit; exCol++)
                    {
                        //1보드 체크
                        if(correctBoard0[correctBoardRow][correctBoardCol] != board[exRow][exCol])
                            wrongPoint[0]++;

                        //2보드 체크
                        if(correctBoard1[correctBoardRow][correctBoardCol++] != board[exRow][exCol])
                            wrongPoint[1]++;

                    }
                    correctBoardCol = 0;
                    correctBoardRow++;
                }

                int tempMinWrongPt = wrongPoint[0] <= wrongPoint[1] ? wrongPoint[0] : wrongPoint[1];
                if(minWrongPt > tempMinWrongPt)
                    minWrongPt = tempMinWrongPt;


            }
        }

        System.out.println(minWrongPt);
    }


}

 

 

도움된 곳:

https://hoho325.tistory.com/89

 

아래는 문제 본문이다.

---

 

체스판 다시 칠하기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

64756

30434

24519

47.157%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1 복사

1

예제 입력 2 복사

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

예제 출력 2 복사

12

예제 입력 3 복사

8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

예제 출력 3 복사

0

예제 입력 4 복사

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

예제 출력 4 복사

31

예제 입력 5 복사

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB

예제 출력 5 복사

0

예제 입력 6 복사

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

예제 출력 6 복사

2

예제 입력 7 복사

11 12
BWWBWWBWWBWW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBWWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW

예제 출력 7 복사

15