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

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

 

문제

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

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

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

 

입력

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

 

출력

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

 

예제	입력	출력
1	8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	1
2	10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB	12
3	8 8 BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB	0
4	9 23 BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBW	31
5	10 10 BBBBBBBBBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBWBWBWBWB BWBWBWBWBB BBBBBBBBBB	0
6	8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWWWB BWBWBWBW	2
7	11 12 BWWBWWBWWBWW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW BWWBWBWWWBWW WBWWBWBBWWBW BWWBWBBWWBWW WBWWBWBBWWBW	15

 

해결 코드

import java.util.Scanner;

public class Main {
	
	public static int findError(char[][] set, int i, int j, char std) {
		int error = 0;
		
		for(int s=i; s<i+8; s++) {
			for(int k=j; k<j+8; k++) {
				if((s + k) % 2 ==0) {
					if (set[s][k] == std) continue;
					else error++;
				}
				else {
					if (set[s][k] == std) error++;
					else continue;
				}
			}
		}
		
		return error;
	}
	
	public static void main(String args[]) {
		//M*N -> B/W로 채워져있음
		//8*8 크기에서 체스판 모양과 다른 칸이 최소인 개수 고르기
		//완전탐색? slidiing window?
		//DP를 이용하면 속도를 높일 수 있다?
		
		//DP table -> M - 8 * N - 8
		//한칸씩 왼쪽, 오른쪽 이동
		//DP table에는 해당 인덱스 기준으로 오른쪽, 아래 8*8 체스판에서 고쳐야 할 개수 저장
		//다음 table 갱신은 ....
		//DP 식 못 세워서 포기
		 
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		
		
		char[][] set = new char[n][m];
		
		for(int i=0; i<n; i++) {
			String temp = scanner.next();
			for(int j=0; j<m; j++) set[i][j] = temp.charAt(j);
		}
		
		int ans = Integer.MAX_VALUE;
		
		for(int i=0; i<=n-8; i++) {
			for(int j=0; j<=m-8; j++) { // 완전 탐색
				ans = Math.min(ans,  Math.min(findError(set, i, j, 'W'), findError(set, i, j, 'B')));
			}
		}
		
		System.out.println(ans);
		
	}
}

 

이 문제는 M×N 크기의 보드에서 8×8 크기의 부분 보드를 선택하여 체스판으로 만들 때 다시 칠해야 하는 최소 개수를 구하는 문제를 해결해야 한다. 완전 탐색과 체스판의 규칙을 활용한 브루트포스 방식으로 해결되었다.

 

 

 

---

1. 자료구조 분석

char[][] set

• 설명: M×N 크기의 보드를 저장하는 2차원 배열이다.

• 용도: 각 칸의 색깔을 저장한다. (W: 흰색, B: 검은색)

• 크기: 최대 M × N

 

 

 

---

2. 알고리즘 분석

전체 개요

• 이 문제는 8×8 체스판을 만들기 위해 보드에서 8×8 크기의 부분 보드를 선택하고, 이를 체스판으로 고칠 때 최소한의 칸 수를 찾는 문제이다.

• 체스판은 두 가지 경우가 있다.

1. 왼쪽 위가 흰색인 경우 (W로 시작)

2. 왼쪽 위가 검은색인 경우 (B로 시작)

 

1) findError() 함수

public static int findError(char[][] set, int i, int j, char std) {
		int error = 0;
		
		for(int s=i; s<i+8; s++) {
			for(int k=j; k<j+8; k++) {
				if((s + k) % 2 ==0) {
					if (set[s][k] == std) continue;
					else error++;
				}
				else {
					if (set[s][k] == std) error++;
					else continue;
				}
			}
		}

 

• 목적:

(i, j)를 왼쪽 위로 하는 8×8 부분 보드를 기준으로 체스판을 만들 때 잘못 칠해진 칸의 개수를 계산한다.

• 매개변수:

• set: 보드 배열

• i, j: 8×8 부분 보드의 왼쪽 위 좌표

• std: 시작 색 (W 또는 B)

• 로직:

• std가 W일 때: 체스판의 첫 번째 칸이 W가 되어야 한다.

• std가 B일 때: 체스판의 첫 번째 칸이 B가 되어야 한다.

• 체스판 규칙에 따라, 인덱스 (s, k)가 짝수일 때는 std와 동일한 색이어야 하고, 홀수일 때는 반대 색이어야 한다.

• 이 규칙을 이용해 잘못 칠해진 칸의 개수를 계산한다.

• 시간 복잡도: O(8 × 8) = O(64) (상수 시간)

 

---

 

2) main() 함수

public static void main(String args[]) {
		 
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		
		
		char[][] set = new char[n][m];
		
		for(int i=0; i<n; i++) {
			String temp = scanner.next();
			for(int j=0; j<m; j++) set[i][j] = temp.charAt(j);
		}
		
		int ans = Integer.MAX_VALUE;
		
		for(int i=0; i<=n-8; i++) {
			for(int j=0; j<=m-8; j++) {
				ans = Math.min(ans,  Math.min(findError(set, i, j, 'W'), findError(set, i, j, 'B')));
			}
		}
		
		System.out.println(ans);
		
	}

 

• 입력 처리:

• 첫째 줄: n (행)과 m (열) 입력

• 둘째 줄부터 n개의 문자열로 보드 정보 입력

• 로직:

• 8×8 부분 보드를 완전 탐색한다.

• 시작 위치는 (i, j)로, i는 0부터 n-8까지, j는 0부터 m-8까지 이동

• 각 (i, j)에 대해 findError() 함수를 두 번 호출:

1. 왼쪽 위가 W일 때(std = 'W')

2. 왼쪽 위가 B일 때(std = 'B')

• 두 경우 중 작은 값을 선택

• 최종적으로 최소값을 출력

• 시간 복잡도:

• 8×8 부분 보드를 완전 탐색 → (n-7) × (m-7)

• 각 부분 보드마다 findError() 두 번 호출 (O(64) × 2)

• 총 시간 복잡도: O((n-7) × (m-7) × 128) ≈ O(n × m)

 

 

 

---

3. 최적화 및 개선점

• 현재 방식의 장점:

• 완전 탐색으로 모든 경우를 확인하므로 정확한 결과를 보장한다.

• O(n × m) 시간 복잡도로 충분히 빠르다.

• 개선 가능성:

• DP (Dynamic Programming) 사용: 현재는 DP를 사용하지 않았지만, 중복된 계산을 줄이기 위해 DP를 적용할 수 있다.

• 예를 들어, 누적 합이나 부분 체스판 상태를 미리 저장해두면 속도를 더 높일 수 있다.

• 슬라이딩 윈도우 기법:

• 한 칸씩 이동할 때 변화하는 부분만 계산하면 중복된 연산을 피할 수 있다.

• 기타 팁:

• 문자열 비교 시 mode == "plus"처럼 == 대신 .equals() 사용이 더 적절하다. (자바에서 ==는 객체의 참조 주소를 비교)

 

 

 

---

(+) DP (Dynamic Programming) 풀이

 

핵심 아이디어

• 누적 합을 이용해 체스판 패턴에 맞지 않는 칸의 개수를 미리 구해둔다.

• dp[i][j]: (0, 0)에서 (i, j)까지 체스판 규칙에 맞지 않는 칸의 개수

• 8×8 보드를 구할 때는 dp 배열을 이용해 상수 시간에 다시 칠해야 하는 칸의 개수를 계산한다.

 

접근 방법

1. 누적 합 배열(dp 배열) 생성

2. dp[i][j]에는 (0, 0)에서 (i, j)까지 체스판 규칙에 맞지 않는 칸의 개수를 저장

3. 각 8×8 부분 보드에 대해 dp 배열을 이용해 상수 시간에 고쳐야 할 칸 수를 계산

4. W로 시작할 때와 B로 시작할 때 모두 계산하고 최소값을 갱신

 

DP 코드

import java.util.Scanner;

public class Baekjoon1018_DP {
    static char[][] board;
    static int[][] dpW;
    static int[][] dpB;
    
    // DP 배열 생성
    public static void makeDP(int n, int m) {
        dpW = new int[n+1][m+1];
        dpB = new int[n+1][m+1];
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                int addW = 0;
                int addB = 0;
                
                if ((i + j) % 2 == 0) { // 짝수
                    if (board[i][j] != 'W') addW++;
                    if (board[i][j] != 'B') addB++;
                } else { // 홀수
                    if (board[i][j] != 'B') addW++;
                    if (board[i][j] != 'W') addB++;
                }
                
                dpW[i+1][j+1] = dpW[i][j+1] + dpW[i+1][j] - dpW[i][j] + addW;
                dpB[i+1][j+1] = dpB[i][j+1] + dpB[i+1][j] - dpB[i][j] + addB;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        
        board = new char[n][m];
        
        for (int i = 0; i < n; i++) {
            String line = scanner.next();
            for (int j = 0; j < m; j++) {
                board[i][j] = line.charAt(j);
            }
        }
        
        makeDP(n, m);
        
        int minError = Integer.MAX_VALUE;
        
        for(int i = 0; i <= n-8; i++) {
            for(int j = 0; j <= m-8; j++) {
                int errorW = dpW[i+8][j+8] - dpW[i][j+8] - dpW[i+8][j] + dpW[i][j];
                int errorB = dpB[i+8][j+8] - dpB[i][j+8] - dpB[i+8][j] + dpB[i][j];
                minError = Math.min(minError, Math.min(errorW, errorB));
            }
        }
        
        System.out.println(minError);
    }
}

 

시간 복잡도 분석

• DP 배열 생성: O(n × m)

• 부분 보드 탐색: O((n-7) × (m-7))

• 총 시간 복잡도: O(n × m)

• 공간 복잡도: O(n × m) (보드와 DP 배열 저장)