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

주재완·2024년 3월 23일

백준

목록 보기

6/8

문제 링크 : https://www.acmicpc.net/problem/1018
티어 : 실버 4
알고리즘 분류

브루트포스 알고리즘

누적합

스터디 겸 작성하게 된 문제로 기본적인 구현 능력과 누적합 개념을 접하기에 좋은 문제라 생각합니다. 개인적으로 실버 4치고는 난이도가 있는 문제라고 생각하고, 누적합으로 접근하는 방법은 최솟값 처리하는게 까다로워서 선정하게 되었습니다.

이문제의 상위호환 문제로는 백준 25682가 있고, 해당 문제는 단순 구현만으로는 시간초과가 납니다.

하지만, 1018번 문제는 단순 구현 만으로 시간초과가 발생하지 않습니다. 따라서 단순 구현 아이디어로 이 문제를 우선 풀이하고, 누적합은 깃커밋으로 첨부하겠습니다.

단순 구현

단순 구현 및 완전 탐색, 브루트포스로 이 문제를 해결이 가능합니다. 아이디어는 다음과 같습니다.

우선 전체적인 개략적인 이미지는 N X M의 전체 판에서 8 X 8의 보드를 가져옵니다. 이 가져오는 경우에는 8 X 8보드의 가장 왼쪽 위 기준으로 가로 및 세로 길이가 8이기에 행은 0에서 N-8까지, 열 인덱스는 0에서 M-8 까지입니다.

헷갈리시면 9 X 9 보드로 간단하게 생각해보면 됩니다. 여기서 8 X 8 보드를 추출할 때, 8 X 8보드 의 왼쪽 위 기준으로 (0, 0), (1, 0), (0, 1), (1, 1)이 가능합니다. 여기서 1을 잘 생각해보면 1 == 9-8 이므로 범위를 확인할 수 있습니다.

그러면 각 보드를 모두 돌아서 칠하는 횟수의 최솟값을 찾으면 됩니다. 간단한 로직은 아래와 같습니다.

int min = m * n; // 최솟값이 아무리 커도 판 전체 색칠하는 것보다 클 수는 없습니다.
for	(int i = 0; i <= N - 8; i++) {
	for (int j = 0; j <= M - 8; j++) {
    	// 여기는 8 X 8 보드 내부에서 칠하는 횟수의 최솟값을 처리할 로직
        // 기존 min과 새롭게 얻는 8 X 8 보드 내부에서 칠하는 횟수의 최솟값과 비교
    }
}

그러면 각 과정에서 가져온 8 X 8보드에 대해서 살펴보도록 하겠습니다. 이 부분은 따로 메소드로 빼는 편이 좋습니다.

8 X 8 보드 내부

8 X 8 보드 내부는 크게 두가지 경우의 수가 있습니다

B로 시작하는 경우

W로 시작하는 경우

8 X 8 보드 내부에서 상대적인 인덱스를 기준으로 하면 인덱스는 행과 열 모두 0에서 7까지의 값을 가지게 됩니다. 그러면 기준은 (0,0)이 B인 경우와 W인 경우로 나뉩니다.

각 케이스를 살펴보면

B인 경우 시작점은 물론이고 행의 인덱스와 열의 인덱스의 합이 짝수인 경우에는 B 홀수라면 B가 아닙니다.

W인 경우 시작점은 물론이고 행의 인덱스와 열의 인덱스의 합이 짝수인 경우에는 W 홀수라면 W가 아닙니다.

정말로 딱 하나만 다릅니다. 즉 매개변수 color 같은 것으로 char 값을 받아왔을 때, 해당 위치에 있는 인덱스가 홀수인지 짝수인지만 판별하면 됩니다.

주의할 것은 오히려 성공을 했을 때는 칠하는 횟수가 증가하지 않고 올바르지 않은 색일때 색을 칠해야 한다는 것입니다. 즉, 칠하는 횟수를 구하는 변수 count라 지정하면, count 는 올바른 색일 때는 그대로, 아니면 count = count + 1 해야 됩니다. 이를 메소드로 작성해보겠습니다.

// 현재 정확한 위치를 구하기 위해 시작점의 절대 좌표 (row, col)을 가지고 옵니다.
// 시작점의 상대 좌표 : (0, 0), 절대 좌표 : (row, col)
public static int getMinPaint(char color, int row, int col) {
   	int count = 0;
    for(int i = 0; i < 8; i++) {
    	for(int j = 0; j < 8; j++) {
    		if((i + j) % 2 == 0) {
            	// 짝수일 때는 시작점과 같은 색깔인 경우가 정상
                // 다른 케이스에 대해서 색칠해야되므로 이 때 count + 1을 해줍니다.
	    		count = (board[row + i][col + j] != color) ? count + 1 : count;
	    	} else {
                // 홀수일 때는 시작점과 다른 색깔인 경우가 정상
                // 같은 케이스에 대해서 색칠해야되므로 이 때 count + 1을 해줍니다.
	    		count = (board[row + i][col + j] == color) ? count + 1 : count;
	    	}
    	}
    }

    return count;
}

전체코드

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

public class Main {
	private static char[][] board;
    
    public static void main(String[] args) throws IOException {
        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());
        
        board = new char[n][m];
        
        for(int i = 0; i < n; i++) {
        	board[i] = br.readLine().toCharArray();
        }
        
        int min = m * n; // 최솟값이 아무리 커도 판 전체 색칠하는 것보다 클 수는 없습니다.
        for(int row = 0; row <= n - 8; row++) {
        	for(int col = 0; col <= m - 8; col++) {
            	// 여기는 8 X 8 보드 내부에서 칠하는 횟수의 최솟값을 처리할 로직
        		int tmp = Math.min(getMinPaint('B', row, col), getMinPaint('W', row, col));
        		// 기존 min과 새롭게 얻는 8 X 8 보드 내부에서 칠하는 횟수의 최솟값과 비교
                min = Math.min(min, tmp);
        	}
        }
        
        System.out.println(min);
        br.close();
    }
    
    // 현재 정확한 위치를 구하기 위해 시작점의 절대 좌표 (row, col)을 가지고 옵니다.
	// 시작점의 상대 좌표 : (0, 0), 절대 좌표 : (row, col)
    public static int getMinPaint(char color, int row, int col) {
    	int count = 0;
    	for(int i = 0; i < 8; i++) {
    		for(int j = 0; j < 8; j++) {
    			if((i + j) % 2 == 0) {
                	// 짝수일 때는 시작점과 같은 색깔인 경우가 정상
                	// 다른 케이스에 대해서 색칠해야되므로 이 때 count + 1을 해줍니다.
	    			count = (board[row + i][col + j] != color) ? count + 1 : count;
	    		} else {
                	// 홀수일 때는 시작점과 다른 색깔인 경우가 정상
                	// 같은 케이스에 대해서 색칠해야되므로 이 때 count + 1을 해줍니다.
	    			count = (board[row + i][col + j] == color) ? count + 1 : count;
	    		}
    		}
    	}

    	return count;
    }
}