알고리즘 문제풀이

[백준/BOJ] 1018 체스판 다시 칠하기

dev-byul 2022. 2. 18. 22:58

문제 출처 : https://www.acmicpc.net/problem/1018

문제 정보

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2초 128 MB 59362 27635 22309 46.764%

문제 설명

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

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

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

입력

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

  • 첫째 줄에 N과 M의 숫자가 주어집니다. ( N , M ≥ 8 ) ( N , M ≤ 50 )
  • 둘쨰 줄부터는 N * M 형태의 보드판이 주어집니다.
  • B 는 검은색이며, W 는 흰색입니다.

출력

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

예제

알고리즘

입력 받은 martix 에서 8 X 8의 크기만큼을 잘랐을때 새로 칠해야 하는 부분에 대해 counting 하는 문제입니다. 이중 가장 적게 칠한 경우의 수를 구해 반환해주는 프로그램을 만드는 것입니다.

문제에서 8 X 8 크기는 아무데서나 골라도 된다. 와 문제 유형 브루트포스 알고리즘 을 주목해야 합니다.

y = 10, x = 10 칸의 martix를 입력 받았으며, 모든 색상이 W 일 경우를 가정 하겠습니다.

범위를 지정하는 경우의 수

경우의 수는 ( x 축 값 - 7 ) X ( y축 값 - 7) 인것을 확인 할 수 있습니다.

체스판의 크기는 8 X 8 이기때문에 각 y축과 x축의 길이에서 -7을 해줍니다.

위의 그림을 보면 현재 선택된 칸이 경우의 수가 1을 소모하게 됩니다. 이후 x - 8 부분들로 한칸씩 옮겨 경우의 수를 갖게 된다면 경우의 수는 위에서 언급했듯이 ( x 축 값 - 7 ) X ( y축 값 - 7)이 됩니다.

색을 칠하는 경우의 수

생각하기 쉬운 최대 경우의 수는 32입니다. 이러한 경우는 보드판에서 자른 체스판이 전체칸이 64개가 모두 동일한 색상일 경우입니다. 이때 맨 첫칸이 어떠한 색상인지 확인 이후 색을 칠합니다.

예를 들어 체스판의 크기가 4 X 4 일 경우 체스판의 개수는 16개가 됩니다. 이때 모두 동일한 색상 일 경우 (4 X 4) / 2 의 개수만큼 색을 칠해야 합니다.

  • 첫번째 칸이 검정인 경우 칠해야 하는 개수 = 8
  • 첫번째 칸이 흰색인 경우 칠해야 하는 개수 = 8

조금더 복잡하게 해서 이러한 경우의 수가 아닌 다른 조건의 경우의 수를 한번 살펴 보겠습니다.

조금 더 컴퓨터 스럽게 생각해보자.

첫번째 칸이 검정인 경우

첫번째 칸이 흰색인 경우

첫번째 칸만 다른 같은 색상으로 도포되어 있는 체스판입니다.

이때 첫번째 비교대상의 색상은 변경하지 않는다는 가정으로 코드를 작성 할 경우

  • 첫번째 칸이 검정인 경우 칠해야 하는 개수 = 1
  • 첫번째 칸이 흰색인 경우 칠해야 하는 개수 = 14

A. 최대 경우의 수는 체스판의 개수 - 1와 동일하다.
일반적으로 생각할때 최대의 경우의 수는 체스판의 개수 / 2가 최대의 경우의 수입니다. 하지만 컴퓨터적으로 생각하면 첫번째 칸을 제외한 모든 체스판의 개수만큼 모두 색을 변경해야 하는 것이 최대의 경우의 수가 나오게 됩니다. - 이부분은 코드로 보면서 조금 더 자세히 보도록 하겠습니다.

첫번째 칸이 검정인 경우 칠해야 하는 개수는 1개 이고, 흰색인 경우에는 14개가 나오게 됩니다. 우리는 이중 더 작은 색을 칠해야하는 경우의 수를 카운팅을 하여 다른 범위의 경우의 수에서 또 다시 한번 카운팅 하여 그 전에 구한 색을 칠해야 하는 경우의 수와 비교하한 뒤 가장 작은 수를 구하면 됩니다.

작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static String[][] matrix;

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        matrix = new String[y][x];

        for (int i = 0; i < matrix.length; i++) {
            String str = br.readLine();
            matrix[i] = str.split("");
        }

        int painting_min = 63;
        for (int y_index = 0; y_index < y - 7; y_index++) {
            for (int x_index = 0; x_index < x - 7; x_index++) {
                painting_min = Math.min(painting_min,find(y_index, x_index));
            }
        }
        System.out.println(painting_min);
    }

    private static int find(int y_index, int x_index) {
        int end_y = y_index + 8;
        int end_x = x_index + 8;
        int count = 0;

        String TF = matrix[y_index][x_index];
        for (int y = y_index; y < end_y; y++) {
            for (int x = x_index; x < end_x; x++) {
                if (!matrix[y][x].equals(TF)) {
                    count += 1;
                ****}

                if(x+1 == end_x) continue;
                else if (TF.equals("B"))
                    TF = "W";
                else if (TF.equals("W"))
                    TF = "B";
            }
        }

        count = Math.min(count, 64 - count);

        return count;
    }

}

코드 풀이

main 메소드

public static String[][] matrix;

입력 받을 보드판을 모든 객체에서 접근 할 수 있도록 static 영역으로 미리 선언했습니다.

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int y = Integer.parseInt(st.nextToken());
    int x = Integer.parseInt(st.nextToken());

    matrix = new String[y][x];

    for (int i = 0; i < matrix.length; i++) {
        String str = br.readLine();
        matrix[i] = str.split("");
    }

BufferedReader 와 StringTokenizer 를 이용하여 데이터를 입력 받습니다.

  1. StringTokenizer 에는 보드의 y축과 x축의 데이터를 입력 받은 이후 y, x 변수에 할당 합니다.
  2. 보드판의 색상을 입력 받은 후 matrix에 저장합니다.
    int painting_min = 63;
    for (int y_index = 0; y_index < y - 7; y_index++) {
        for (int x_index = 0; x_index < x - 7; x_index++) {
            painting_min = Math.min(painting_min,find(y_index, x_index));
        }
    }

색칠해야 하는 최대 경우의 수를 min 값으로 초기화한 이후 범위를 지정하는 경우의 수 만큼 반복하여 색칠해야 하는 경우의 수를 구합니다.

  1. 범위를 지정한 이후 색칠해야 하는 경우의 수를 구합니다.
  2. 구한 경우의 수와 현재 저장되어 있는 경우의 수 중 더 작은 수를 저장합니다.
  3. y_index 와 x_index 에서 -7 한 이유는 비교 연산자와 연관이 있습니다.
    1. [ a < b ] a 는 b 미만의 수 입니다.
    2. [ a ≤ b ] a 는 b 이하의 수 입니다.

find 메소드

int end_y = y_index + 8; 
int end_x = x_index + 8;

이제 범위 내에서 색을 칠해야 하는 경우의 수를 구해야 합니다. 이때 최대 범위를 +8 만큼 지정을 합니다.

여기서 end 값은 왜 +8 을 했냐면, y 축과 x 축이 각각 [0, 0] 이 들어왔다 쳤을때 [7, 7]까지 계산을 해야합니다.

그렇기 때문에 +8을 했습니다.

int count = 0; 
String TF = matrix[y_index][x_index];

색칠을 하는 경우의 수를 카운팅 할 변수와 현재 범위의 맨 첫번째 칸의 색상(비교할 색상)을 가져옵니다.

for (int y = y_index; y < end_y; y++) {
    for (int x = x_index; x < end_x; x++) {
        // 1
        if (!matrix[y][x].equals(TF)) {
            count += 1;
        }

        // 2
        if(x+1 == end_x) continue;
        else if (TF.equals("B"))
            TF = "W";
        else if (TF.equals("W"))
            TF = "B";
    }
}
  1. 범위 내에서 현재 비교할 색상과 일치 하지 않을 경우 색칠을 해야 하는 경우의 수이니 count 를 1 추가 해줍니다.
  2. 라인의 첫번째 색상은 그 전라인의 마지막 색상과 같은 색상입니다. 나머지 색상은 그 전색상과 반대의 색상을 가지게 됩니다.
    1. x 가 마지막 경우의 수일 경우 비교할 색상은 변경하지 않습니다.
    2. 비교 색상이 검정일 경우 다음 비교색상으로 흰색으로 변경 혹은 이와 반대의 경우로 설정합니다.
    3. 4X2 의 라인이 있을 경우 이를 한줄로 펼치게 되면, 4(n)의 색상과 4(n)+1의 색상이 동일 색상인 것을 확인 할 수 있습니다.

A. 최대 경우의 수는 체스판의 개수 - 1과 동일하다.
우리는 TF 측에 첫번째 칸의 색상을 작성해주었습니다. 코드 1번과 2번을 보면 첫번째 칸의 색상 기준으로 하여금 개수를 구하고 있는 것을 확인 할 수 있습니다. 이때 만약 첫번째 줄이 WWBWBWBW 일 경우 맨 첫번째칸 W만 변경을 하면 되지만, 코드는 WBWBWBWB 로 equals 를 비교하여 카운팅을 시작하게 됩니다. 즉 이때 카운팅은 7개가 되는 것입니다.

그림으로 좀더 쉽게 표현하자면 다음과 같습니다.

사람이라면 그냥 첫번째 칸만 색상을 변경하면 된다라는 것을 바로 알 수 있습니다. 하지만 코드로 작성을 하면 상당히 복잡한 코드가 나오게 됩니다.

// 예시 코드  
// matrix 는 bloone 형 배열이며 , TF 는 true 값일 경우 
if(matrix[y][x+1].equals(TF) && matrix[y+1][x].equals(TF) && x+1 !+ x.length) matrix[y][x] = !TF;

이러한 방식은 브루트포스 방식도 아니며, 코드 또한 너무 복잡해지며, 무수한 조건문들이 줄비하게 될 것입니다.

조금 이야기가 새나갔지만 다시 돌아와서 첫번째 칸이 검정인 경우 코드는 검정일 경우의 수를 위의 그림처럼 비교를 해가며 카운팅을 할 것입니다. 그렇게 될 경우 첫번째 칸을 제외한 나머지 칸들을 모두 바꾸게 될 것입니다.

count = Math.min(count, 64 - count);

우리는 count 에 현재 색상이 TF 일 경우의 수만을 구해놨습니다.

TF 색상의 반대는 어떻게 하면 구할 수 있을 것인가??

이는 간단하게 풀수 있습니다. 체스판의 총합 개수 에서 우리가 카운팅한 개수를 제외하면 그 반대의 경우의 수를 구할 수 있습니다.

제출 결과

깃허브 주소

https://github.com/AbyulStudy/java_algorithm/blob/master/Class_02/S_1018/Main.java

참고 사이트

https://st-lab.tistory.com/101?category=855026

'알고리즘 문제풀이' 카테고리의 다른 글

[백준/BOJ] 1620 나는야 포켓몬 마스터 이다솜  (0) 2022.03.14

'알고리즘 문제풀이'의 다른글

  • 현재글[백준/BOJ] 1018 체스판 다시 칠하기

관련글

티스토리툴바