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

문제 링크

1018번: 체스판 다시 칠하기

문제 이해

 해당 문제는 '완전 탐색' 문제로써, 풀이 시간이 상당히 오래걸렸습니다. for문으로 다뤄야하는 변수 값이 많았기에 실수하지 않는 것이 중요했습니다. 체스판의 경우 8*8의 크기를 가지게 되는데, N,M에 따라서 체스판이 될 수 있는 경우가 다양하기에 모든 경우를 탐색하는 식으로 문제를 풀이했습니다.

 코드를 풀이했던 핵심 방법은, 처음에 왼쪽 위 꼭지점 좌표를 for문을 기반으로 정하는 것입니다. 이 때, X좌표의 경우 최대 M-8만큼 될 수 있으며, Y좌표의 경우 N-8만큼 후보군으로 지정할 수 있습니다.

 

PPT로 직접 제작한 그림

 

따라서, N=9, M=10일 경우 체스판 시작좌표의 후보는 (0,0), (0,1), (0,2), (1,0), (1,1), (1,2)가 될 수 있습니다.

시작점을 선택한 이후에는 시작점이 "B"로 시작하는 경우, "W"로 시작하는 경우로 풀이했습니다.

 

1. "B"로 시작하는경우

- 체스판의 첫째 행은 "BWBWBWBW" 

- 체스판의 둘째 행은 "WBWBWBWB"

- 그러나, "BBWBWBWB" 와 같은 경우가 생길 수 있으므로 "BWBWBWBW"가 첫째 행인 체스판과 비교해주는 bCheck( ), "WBWBWBWB"가 첫째 행인 체스판과 비교해주는 wCheck( )를 실행하여 바뀐 횟수가 적은 것을 정답으로 출력!

 

2. "W"로 시작하는경우

- 체스판의 첫째 행은 "WBWBWBWB"

- 체스판의 둘째 행은 "BWBWBWBW" 

- 그러나, "WWBWBWBW" 와 같은 경우가 생길 수 있으므로 "BWBWBWBW"가 체스판과 비교해주는 bCheck( ), "WBWBWBWB"가 첫째 행인 체스판과 비교해주는 wCheck( )를 실행하여 바뀐 횟수가 적은 것을 정답으로 출력!

 

최종적으로 시작점 위치에 따라 bCheck( ), wCheck( )를 실행하여 나온 결과 값들을 HashSet을 통해 중복을 제거, 최소 값을 출력하는 식으로 문제를 풀이하였습니다.

문제 코드

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

public class Main {

    public static HashSet<Integer> answer = new HashSet<>();
    public static char black = 'B';
    public static char white = 'W';

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

        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[][] arr = new char[N][M];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            char[] tmp = input.toCharArray();
            for (int j = 0; j < M; j++) {
                arr[i][j] = tmp[j];
            }
        }

        // 탐색 시작, 체스판을 아래방향으로 탐색 후, x좌표를 한칸씩 이동
        for (int i = 0; i <= M - 8; i++) { // x의 시작점
            for (int j = 0; j <= N - 8; j++) {  // y의 시작점
                if (arr[j][i] == 'B') { // 해당 시작점이 B로 시작할 때, "BWBWBWBW"와 "WBWBWBWB" 값을 가져온 후 비교하고자함. 여기에서 j, i의 위치를 헷갈려서 문제 오류가 발생함!
                    bCheck(j, i, arr);
                    wCheck(j, i, arr);
                }
                else { // 해당 시작점이 W로 시작할 때
                    bCheck(j, i, arr);
                    wCheck(j, i, arr);
                }
            }
        }
        // HashSet에서 최소 값을 출력하기!
       System.out.print(Collections.min(answer));
    }

    public static void bCheck(int start_row, int start_col, char[][] Board) { // 시작이 Black일 때, 변경해야하는 횟수 리턴

        int change = 0; // W,B 바뀌어야되는 횟수

        for (int i = start_row; i < start_row + 8; i++) { // y좌표를 선택
            for (int j = start_col; j < start_col + 8; j++) { // x좌표 선택
                if (i % 2 == 0) {   // i가 0,2,4,6 일 때는 "BWBWBWBW" 여야함
                    if (j % 2 == 0) { // j가 0,2,4,6 일 때는 "B"문자가 나와야함
                        // 지금 B문자가 나와야하는데, W인 경우 바뀌어야하므로 change 카운터 증가!
                        if (Board[i][j] == white) {
                            change++;
                        }
                    }
                    else { // j가 1,3,5,7인 경우에는 "W"문자가 나와야하는데 B문자가 나올경우 바뀌어야하므로 change 카운터 증가
                        if (Board[i][j] == black) {
                            change++;
                        }
                    }
                }
                else { // 해당 행 i가 1,3,5,7인 경우 "WBWBWBWB"가 나와야함
                    if (j % 2 == 0) { // j가 0,2,4,6 일 때는 "W"문자가 나와야함
                        if (Board[i][j] == black) {
                            change++;
                        }
                    }
                    else { // j가 1,3,5,7인 경우 "B"문자가 나와야함
                        if (Board[i][j] == white) {
                            change++;
                        }
                    }
                }
            }
        }
        // Hashset에 change 값을 추가하기
        answer.add(change);
    }

    public static void wCheck(int start_row, int start_col, char[][] Board) { // 시작이 White일 때, 변경해야하는 횟수 리턴

        int change = 0; // W,B 바뀌어야되는 횟수

        for (int i = start_row; i < start_row + 8; i++) { // y좌표를 선택
            for (int j = start_col; j < start_col + 8; j++) { // x좌표 선택
                if (i % 2 == 0) {   // i가 0,2,4,6 일 때는 "WBWBWBWB" 여야함
                    if (j % 2 == 0) { // j가 0,2,4,6 일 때는 "W"문자가 나와야함
                        // 지금 W문자가 나와야하는데, B인 경우 바뀌어야하므로 change 카운터 증가!
                        if (Board[i][j] == black) {
                            change++;
                        }
                    }
                    else { // j가 1,3,5,7인 경우에는 "B"문자가 나와야하는데 W문자가 나올경우 바뀌어야하므로 change 카운터 증가
                        if (Board[i][j] == white) {
                            change++;
                        }
                    }
                }
                else { // 해당 행 i가 1,3,5,7인 경우 "BWBWBWBW"가 나와야함
                    if (j % 2 == 0) { // j가 0,2,4,6 일 때는 "B"문자가 나와야함
                        if (Board[i][j] == white) {
                            change++;
                        }
                    }
                    else { // j가 1,3,5,7인 경우 "W"문자가 나와야함
                        if (Board[i][j] == black) {
                            change++;
                        }
                    }
                }
            }
        }
        //HashSet에 change 값 추가하기
        answer.add(change);
    }
}