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

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

1018번: 체스판 다시 칠하기

[난이도]

- Silver 4

 

[알고리즘]

- 부르트 포스

 

[정답 코드]

import org.w3c.dom.html.HTMLParagraphElement;

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

public class Main {
    static char[][] arr;
    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());

        arr = new char[N][M];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = input.charAt(j);
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                answer = Math.min(answer, Math.min(startWhite(i, j), startBlack(i, j)));
            }
        }
        System.out.println(answer);

    }

    static int startWhite(int x, int y) {
        int sum = 0;
        for (int i = x; i < x+8; i++) {
            for (int j = y; j < y+8; j++) {
                if (i % 2 == 0 && j % 2 == 0) {
                    if (arr[i][j] != 'W') {
                        sum++;
                    }
                } else if (i % 2 != 0 && j % 2 == 0) {
                    if (arr[i][j] != 'B') {
                        sum++;
                    }
                } else if (i % 2 == 0 && j % 2 != 0) {
                    if (arr[i][j] != 'B') {
                        sum++;
                    }
                } else {
                    if (arr[i][j] != 'W') {
                        sum++;
                    }
                }
            }
        }

        return sum;
    }

    static int startBlack(int x, int y) {
        int sum = 0;
        for (int i = x; i < x+8; i++) {
            for (int j = y; j < y+8; j++) {
                if (i % 2 == 0 && j % 2 == 0) {
                    if (arr[i][j] != 'B') {
                        sum++;
                    }
                } else if (i % 2 != 0 && j % 2 == 0) {
                    if (arr[i][j] != 'W') {
                        sum++;
                    }
                } else if (i % 2 == 0 && j % 2 != 0) {
                    if (arr[i][j] != 'W') {
                        sum++;
                    }
                } else {
                    if (arr[i][j] != 'B') {
                        sum++;
                    }
                }
            }
        }

        return sum;
    }
}

 

[풀이]

처음엔 2차원 그래프가 나오고 문제흐름상 dfs나 bfs와 4방탐색을 활용하면 풀 수 있겠다! 라고생각했었다. 그런데 풀다보니 그렇게 풀면 코드가 더 짧아지고 시간이 더 짧게 걸릴수는 있겠지만 진짜 부르트하게 풀어도 풀리겠는데? 라는생각이 들어 다른방식으로 풀었다.

 

1. 입력받은 값중 나올 수 있는 보드판들의 시작위치를 i, j로 설정한다.

2. 시작위치가 W로 시작할 때와 B로 시작할 때 두가지 경우를 모두 확인해주어야 한다.

3. 각 말이 놓여야 하는 색과 다른색이 있을경우 sum을 1씩 증가시켜 새로칠하는 경우만 체크해준 후 반환해준다.

4. 두값중에 더 작은값을 Math.min(startWhite(i, j), startBlack(i, j)) 로 찾는다. 그리고 원래 알고있는 최솟값과 새로찾은 최소값을 비교해 정답을 찾는다.