[BOJ_JAVA] 백준 1018번 : 체스판 다시 칠하기 @달깅

 

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

 

 

와 진짜 이 문제 푸는 데 엄~~~~~청 오래 걸렸다..

처음에 deepcopy하고 뭐 별 난리를 다 쳤는데 계속 그 for문도 안돌아가고..ㅠㅠ 오류 뜨고 해서 죽는 줄 알았다.

인덱스가 복잡하니까 포함을 하는 건지 안 하는건지 확인하는 것도 까다롭고 해서 진짜 오래 걸렸고,

일단 처음에는 하나하나 앞이 b이면 뒤가 w 이런식으로 하려다가 진짜 죽을 것 같아서,

구글링을 해보니 아예 저렇게 샘플 2개를 못 박아놓고 그거랑 비교하면서 하면 편하다는 생각이 들었다.

그래서 바로 우회해서 코드를 짜기 시작했는데,

처음에는 temp를 증가시키고 원래 보드 도 수정하는 바람에 계속 오답이 떴다.

근데 생각해보니 원래 보드는 손대면 안되는 것이어서 수정했더니 이제는 그냥 오답이 뜬다...ㅠㅠ

반례를 생각하다 보니, 

첫글자가 b이면 아예 타겟을 B로 시작하는 아이로 못박을 게 아니라,

w가 첫글자일 경우도 타겟으로 지정하여 둘 중의 미니멈을 선택했어야 하는 것이었다..!!

그래서 되게 유레카를 외치고 바로 성공!

시간은 촉박하게 성공해서 좀 더 좋은 코드를 찾아보려고한다.

브루트 포스 너무 어렵다~~

근데 이제 진짜 알고리즘 공부하는 것 같고 그래서 너무 재밌다 ㅎㅎㅎ!

 

---

정답코드

 

 

import java.util.*;

public class Main3 {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        char[][] board=new char[a][b];
        char[][] b1={{'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[][] b2={{'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'}};

        char[][] target=new char[8][8];
        int count=1000;
        int temp1=0;
        int temp2=0;

        for (int i=0; i<a; i++) {
            String line=sc.next();
            for (int j=0; j<b; j++) {
                board[i][j]=line.charAt(j);
            }
        }

    
        for (int i=0; i<=a-8; i++) {
            for (int j=0; j<=b-8; j++) {

                for (int x=i; x<i+8; x++) {
                    for (int y=j; y<j+8; y++) {
                        target=b1;
                        if (board[x][y]!=target[x-i][y-j]) {
                            temp1++;         
                        }                        
                    }
                }

                for (int x=i; x<i+8; x++) {
                    for (int y=j; y<j+8; y++) {
                        target=b2;
                        if (board[x][y]!=target[x-i][y-j]) {
                            temp2++;         
                        }                        
                    }
                }

              
                if (Math.min(temp1, temp2)<count) {
                    count=Math.min(temp1,temp2);
                }
                
                temp1=0;
                temp2=0;
            }
        }

        System.out.println(count);
    }
}