[BOJ] 1018 - 체스판 다시 칠하기 (Java)

알고리즘

• 브루트포스 알고리즘

1. 문제

2. Idea

• 체스판을 만들기 위해서는 한 칸이 상하좌우의 색과 다르면 된다.
• 또한 체스판이 잘못 칠해져 있는 경우 '최소'의 개수로 칠 할 수 있는 부분을 찾아야 한다.
• 경우의 수: (가로 칸 개수 - 7) × (세로 칸 개수 - 7)
• 최소 크기가 8×8 일 때 경우의 수가 1이기 때문에 각 가로 세로별 길이 -7
  

3. 풀이

3.1. 변수 입력 및 생성

• N: 행 수
• M: 열 수
• arr: 체스보드를 나타내는 2차원 배열
• 셀이 흰색('W')이면 true, 검은색('B')이면 false

Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
arr = new boolean[N][M];

3.2. 체스보드 구성

for (int i = 0; i < N; i++) {
	String str = in.next();
			
	for (int j = 0; j < M; j++) {
		if (str.charAt(j) == 'W') {
			arr[i][j] = true;		// W일 때는 true 
		} else {
			arr[i][j] = false;		// B일 때는 false
		}
	}
}

3.3. 체스판 탐색 및 최소 칠하기 연산 찾기

• 8x8 부분 격자를 탐색하면서 find 함수를 호출하여 최소로 다시 칠하는 연산의 횟수를 찾는다.

int N_row = N - 7;
int M_col = M - 7;

for (int i = 0; i < N_row; i++) {
    for (int j = 0; j < M_col; j++) {
        find(i, j);
    }
}
System.out.println(min); // 결과 출력

3.4 find 함수 구현

• 주어진 시작 위치 (x, y)에서부터 8x8 크기의 부분 격자를 탐색하면서 최소의 다시 칠하는 작업 횟수를 찾는다.

• 반복문에서 격자를 탐색하면서 올바른 색이 아닌 경우 count를 증가. 그리고 다음 칸으로 넘어갈 때마다 TF 값을 반대로 변경

• 첫 번째 칸을 기준으로 하는 색칠 횟수와 그 반대되는 색을 기준으로 하는 색칠 횟수 중에서 최솟값을 선택하여 count에 저장합니다. 이후 현재까지의 최솟값(min)과 비교하여 갱신합니다. 이 과정을 모든 가능한 부분 격자에 대해 반복하면 최종적으로 min에는 최소의 다시 칠하는 작업 횟수가 저장되는 방식

  변수 설명

  • end_x, end_y: 현재 부분 격자의 끝 위치를 나타내는 변수. (x+8, y+8)로 설정
  • count: 현재 부분 격자에서 다시 칠해야 하는 칸의 수를 저장하는 변수
  • TF: 현재 탐색 중인 칸의 색을 나타내는 변수로, 첫 번째 칸의 색으로 초기화

public static void find(int x, int y) {
    int end_x = x + 8;
    int end_y = y + 8;
    int count = 0;

    boolean TF = arr[x][y]; // 시작 칸의 색

    for (int i = x; i < end_x; i++) {
        for (int j = y; j < end_y; j++) {
            // 올바른 색이 아닐 경우 count 1 증가
            if (arr[i][j] != TF) {
                count++;
            }
            // 다음 칸은 색이 바뀌므로 true라면 false로, false 라면 true로 값을 변경
            TF = !TF;
        }
        TF = !TF; // 행이 바뀔 때마다 첫 번째 열의 색을 변경
    }

    // 첫 번째 칸을 기준으로 할 때의 색칠 횟수(count)와
    // 첫 번째 칸의 색의 반대되는 색을 기준으로 할 때의 색칠 횟수(64 - count) 중 최솟값을 count에 저장
    count = Math.min(count, 64 - count);

    // 이전까지의 경우 중 최솟값보다 현재 count 값이 더 작을 경우 최솟값을 갱신
    min = Math.min(min, count);
}

4. 전체코드

import java.util.Scanner;
 
public class Main {
 
	public static boolean[][] arr;
	public static int min = 64;
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
		int M = in.nextInt();
 
		arr = new boolean[N][M];
		
        
		// 배열 입력 
		for (int i = 0; i < N; i++) {
			String str = in.next();
			
			for (int j = 0; j < M; j++) {
				if (str.charAt(j) == 'W') {
					arr[i][j] = true;		// W일 때는 true 
				} else {
					arr[i][j] = false;		// B일 때는 false
				}
 
			}
		}
		int N_row = N - 7;
		int M_col = M - 7;
 
		for (int i = 0; i < N_row; i++) {
			for (int j = 0; j < M_col; j++) {
				find(i, j);
			}
		}
		System.out.println(min);
	}
 
	
	public static void find(int x, int y) {
		int end_x = x + 8;
		int end_y = y + 8;
		int count = 0;
 
		boolean TF = arr[x][y];	// 첫 번째 칸의 색 
 
		for (int i = x; i < end_x; i++) {
			for (int j = y; j < end_y; j++) {
 
				// 올바른 색이 아닐경우 count 1 증가 
				if (arr[i][j] != TF) {	
					count++;
				}
				TF = (!TF);
			}
			
			TF = !TF;
		}
		count = Math.min(count, 64 - count);
	
		min = Math.min(min, count);
	}
}