99클럽 코테 스터디 11일차 TIL - 완전 탐색

문제 💁🏻‍♂️

문제 링크 - 백준 1018 체스판 다시 칠하기

해결 과정

이 문제는 처음 읽었을 때, 어떻게 풀어야 할지 생각이 잘 나지 않던 문제였다. 파이썬으로 풀이하면 쉽게 접근하겠다만, 자바로 코테 연습을 하는 과정이어서 입력을 받는 것도 낯설었다.

사고 과정 ❗️

고민을 하던 중에 N과 M 값을 보고 나니, 완전 탐색도 가능하겠다는 생각이 들었다. 즉, 8x8 판이 있다고 생각하고, 범위를 넘어서지 않는 선에서 N x M 너비의 판을 순차적으로 모두 탐색하는 문제로 해석했다. 탐색 범위는 파악했고, 문제 풀이의 로직은 다음과 같이 생각했다.

1. 만약, 'W'로 시작했다면 위치가 (i, j) 라고 했을 때, (i + j) % 2 == 0 즉, y축, x축 인덱스의 합이 짝수이면 'W'여야 한다. 반대로 홀수라면 'B'여야 한다.
2. 만약, 'B'로 시작했다면 위치가 (i, j) 라고 했을 때, (i + j) % 2 == 0 즉, y축, x축 인덱스의 합이 짝수이면 'B'여야 한다. 반대로 홀수라면 'W'여야 한다.
3. 이를 바탕으로 색이 반대로 적혀있는 녀석들의 개수를 'W'로 시작하는 경우, 'B'로 시작하는 경우 2가지로 나누어 계산했다.
4. 각 상황에서 구한 색을 바꿔야 하는 개수들의 최솟값을 구하여 정답을 구한다.

위 생각을 바탕으로 여러 시행착오와 함께 코드를 구현해서 제출했다. 정답 판정을 받았다.

감이 잡히지 않는다면, 주어지는 값의 범위를 통해서 방향성을 잡는 것도 중요한 것 같다 :)

코드

정답 코드

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M, ANS = Integer.MAX_VALUE;
    static char[][] chess;

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

        input();

        solve();

    }

    private static void solve() {

        int wCnt, bCnt;
        int MIN = Integer.MAX_VALUE;
        for (int i = 0; i < N - 8 + 1; i++) {
            for (int j = 0; j < M - 8 + 1; j++) {
                // 모든 케이스마다 8 x 8 체스판을 확인한다.
                wCnt = 0;
                bCnt = 0;
                for (int a = i; a < i + 8; a++) {
                    for (int b = j; b < j + 8; b++) {
                        // 흰색으로 시작한 경우
                        // 짝수 - 흰색 / 홀수 - 검은색
                        if ((a + b) % 2 == 0 && chess[a][b] == 'B')
                            wCnt++;
                        if ((a + b) % 2 == 1 && chess[a][b] == 'W')
                            wCnt++;
                        // 검은색을 시작한 경우
                        // 짝수 - 검은색 / 홀수 - 흰색
                        if ((a + b) % 2 == 0 && chess[a][b] == 'W')
                            bCnt++;
                        if ((a + b) % 2 == 1 && chess[a][b] == 'B')
                            bCnt++;
                    }
                }

                MIN = Math.min(wCnt, bCnt);
                ANS = Math.min(MIN, ANS);
            }
        }

        System.out.println(ANS);
    }

    private static void input() throws IOException {

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        chess = new char[N][M];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                chess[i][j] = line.charAt(j);
            }
        }
    }
}

Reference

• 내 머릿 속