[JAVA / 자바] 백준 1018번 - 체스판 다시 칠하기

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8 × 8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8 × 8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

---

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

---

문제 접근 방법

내용

---

JAVA 코드 풀이

- BufferedReader

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

public class Main {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int col = Integer.parseInt(st.nextToken());
        int row = Integer.parseInt(st.nextToken());
        String board[] = new String[col];
        for(int i=0; i<col; i++)
            board[i] = br.readLine();
        int min = Integer.MAX_VALUE;
        int cnt1, cnt2;
        for(int i=0; i<col-7; i++)
            for(int j=0; j<row-7; j++){
                cnt1=0;
                cnt2=0;
                for(int p=i; p<i+8; p++)
                    for(int q=j; q<j+8; q++){
                        if(p % 2 == 0){
                            if(q % 2 == 0){
                                if(board[p].charAt(q) == 'W')
                                    cnt1++;
                                else
                                    cnt2++;
                            }
                            else{
                                if(board[p].charAt(q) == 'B')
                                    cnt1++;
                                else
                                    cnt2++;
                            }
                        }
                        else{
                            if(q % 2 == 0){
                                if(board[p].charAt(q) == 'B')
                                    cnt1++;
                                else
                                    cnt2++;
                            }
                            else{
                                if(board[p].charAt(q) == 'W')
                                    cnt1++;
                                else
                                    cnt2++;
                            }
                        }
                    }
                min = Math.min(min, Math.min(cnt1, cnt2));
            }
        System.out.println(min);
    }
}

 

- Scanner

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int col = input.nextInt();
        int row = input.nextInt();
        String board[] = new String[col];
        for(int i=0; i<col; i++)
            board[i] = input.next();
        int min = Integer.MAX_VALUE;
        int cnt1, cnt2; // cnt1과 cnt2는 서로 반전색 관계 ex) WBW / BWB 이런식
        for(int i=0; i<col-7; i++)
            for(int j=0; j<row-7; j++){ // 체스판은 8X8 사이즈이므로 입력이 이보다 크면 최대한 적게 수정해도 되는 방향으로 자름
                cnt1=0;
                cnt2=0;
                for(int p=i; p<i+8; p++) // 해당 영역을 체스판으로 만들려면 얼마나 수정해야 하는지 찾음
                    for(int q=j; q<j+8; q++){
                        if(p % 2 == 0){
                            if(q % 2 == 0){
                                if(board[p].charAt(q) == 'W')
                                    cnt1++;
                                else
                                    cnt2++;
                            }
                            else{
                                if(board[p].charAt(q) == 'B')
                                    cnt1++;
                                else
                                    cnt2++;
                            }
                        }
                        else{
                            if(q % 2 == 0){
                                if(board[p].charAt(q) == 'B')
                                    cnt1++;
                                else
                                    cnt2++;
                            }
                            else{
                                if(board[p].charAt(q) == 'W')
                                    cnt1++;
                                else
                                    cnt2++;
                            }
                        }
                    }
                min = Math.min(min, Math.min(cnt1, cnt2)); // 최소 수정 횟수 찾기
            }
        System.out.println(min); // 모든 경우의 최소 수정 횟수 출력
    }
}

코드 실행 결과

BufferedReader코드 실행 결과

Scanner코드 실행 결과

---

후기

입력이 조금이라도 많아지면 Scanner함수보다 BufferedReader함수가 훨씬 시간이나 메모리 측면에서 효율적이다.반면에 코드 길이가 조금 길어지고 BufferdReader함수는 문자열 입력밖에 받지 못하고 입력도 한 줄씩 받아야만 한다.BufferedReader함수로 정수형을 입력받을 땐 형 변환을 해줘야 하는데 형 변환을 할 때 형 변환은 데이터 크기에 따라 오버플로우가 일어나 의도와 다르게 값이 반환될 수 있다. 따라서 항상 형 변환 시에는 주의하면서 사용하여야 한다.

---

문제 원본

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