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

 

---

문제

• 체스판은 각 칸이 검은색 혹은 흰색으로 칠해지며, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 함.
• 이런 조건으로 M x N 사이즈의 보드판이 주어질 때, 8 x 8 사이즈의 체스판을 만들기 위해 칠해진 색을 변경하는 최소 횟수를 구하는 문제.

 

아이디어

• 모든 경우의 수를 탐색하는 완전 탐색으로 문제를 해결한다.
• 입력을 2차원 배열 안에 넣고, 8 x 8 사이즈의 체스판을 입력된 보드 위에서 이동시키며 모든 경우를 따져 최소값을 찾는다.
• 첫번째 줄이 "BWB~" 인 경우도 있고, "WBW" 인 경우도 있으므로 두가지 경우 모두 별도로 바꿔야 하는 색 수를 카운트한다.

체스판을 이동시켜가며 모든 경우의 수를 탐색한다.

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        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());

        char[][] chess = new char[N][M];
        
        // 입력받은 문자열의 보드 판을 character 배열로 변환 후 저장
        for(int i=0; i<N; i++) {
            chess[i] = br.readLine().toCharArray();
        }
        
        // 시작이 'W'인 체스판, 'B'인 체스판을 각각 따로 카운트함
        int cnt1 = 0;
        int cnt2 = 0;
        
        // 최솟값 비교를 위해 정답을 가장 큰 수로 초기화
        int answer = Integer.MAX_VALUE;
        
        // 체스판 이동
        for(int i=0; i<N-7; i++) {
            for(int j=0; j<M-7; j++) {
                cnt1 = 0;
                cnt2 = 0;
                
                // 체스판 위치가 고정되었으니, 바꿔야 하는 칸 수 카운트
                for(int x=0; x<8; x++) {
                    for(int y=0; y<8; y++) {
                        // 1, 3, 5, ...과 같이 홀수번째 행 검사 (인덱스로 치면 짝수번)
                        if((i+x)%2==0) {
                          
                            // 홀수번째 열 검사
                            if((j+y)%2==0) {
                                // 체스판 1 일때, 변경 횟수 카운트
                                if(chess[i+x][j+y] != 'W') {
                                    cnt1++;
                                }
                                // 체스판 2 일때, 변경 횟수 카운트
                                else {
                                    cnt2++;
                                }
                            }
                            // 짝수번째 열 검사
                            else {
                                if(chess[i+x][j+y] != 'B') {
                                    cnt1++;
                                }
                                else{
                                    cnt2++;
                                }
                            }
                        }
                        /// 2, 4, 6, ...과 같이 짝수번째 행 검사
                        else {
                            if((j+y)%2==0) {
                                if(chess[i+x][j+y] != 'B') {
                                    cnt1++;
                                }
                                else {
                                    cnt2++;
                                }
                            }
                            else {
                                if(chess[i+x][j+y] != 'W') {
                                    cnt1++;
                                }
                                else{
                                    cnt2++;
                                }
                            }
                        }
                    }
                }
                
                // 체스판 1, 2를 각각 만들때 바꾸어야 하는 칸 수중, 최솟값으로 정답 갱신
                answer = Math.min(answer, Math.min(cnt1, cnt2));
                
                // 가장 작은 값을(하나도 안바꿔도 될 때) 탐색했으면 종료
                if(answer == 0) {
                    System.out.println(answer);
                    return;
                }
            }
        }
        System.out.println(answer);
    }
}

 

 

채점 결과

1018번 채점 결과

기타

• 시간초과가 날 줄 알았는데.... 시간 복잡도에 대한 학습이 더 필요한 것 같다.
• 완탐은 위대하다.

 

문제 링크

• 1018번: 체스판 다시 칠하기 (acmicpc.net)