[BAEKJOON] 25682 체스판 다시 칠하기 2

문제 요약

• 알고리즘 분류: 구간합, 누적합, 수학
• 난이도: Gold5
• 문제내용:
  • N × M 보드판에서  K × K 크기인 보드로 잘라서 다시 색칠한다.
  • 최소한의 칠해야 하는 개수를 구해라
• 사이트 : https://www.acmicpc.net/problem/25682

25682번: 체스판 다시 칠하기 2

문제풀이

이번 문제는 데이터의 개수가 최대 2000  × 2000이고 제한시간이 1초라서 완전 탐색으로 하면 시간이 초과된다. 그래서

 2차원 배열 구간합을 응용해야 된다. 구간합에 대한 이론은 아래의 사이트에 참조하면 된다.

https://jih3508.tistory.com/50

[알고리즘 이론] 구간합, 누적합(prefix sum)

문제 접근 방법

 막상 위에 문제는 구간합, 누적합이론으로 접근하기에는 힘들수 있다. 이유는 체스판의 위, 아래, 오른쪽, 왼쪽 색깔이 교차가 되어야 되기 때문에 전체 보드판의  봐야되는 경우의 수가 많아서 어떻게 구간합이랑 연결해서 풀어야 할지 생각이 안날 것이다. 하지만 방법만 알면 쉽기때문에 생각만 잘하면된다. 

체스판

 체스판은 2가지 종류가 있다. 맨 위 왼쪽은 검은색일 경우 흰색일 경우가 있다. 그리고 행 + 열을 합쳐서 홀 수이면 다른색 짝수이면 같은 색이라는 것을 알수 있다.  그 다음에는 위에 2가지 경우와 현제 문제에서 나오는 판을 이랑 비교해서 차이가 가장 적은 부분을 가져올 생각이다.

 

맨 오른쪽 그림은 위의 예제를 그림으로 나타낸것이다.

 위 문제의 예제 1번을 표로 나타낸것과 2가지 정상인 체스판과 비교할것이다,

 

 0은 같은 경우 1은 다른 경우로 표시한것이다. 여기서 부터 2차원 배열 누적합을 할것이다. 그러면 2가지 경우중에서 가장 같은 영역을 구하면 된다.

누적합 구한 결과

 위에 누적합의 결과이고 두 가지 영역에서 각 3 × 3 영역의 구간합중에 가장 작은 값을 구하면 된다. 누적합과 구간합의 계산 방법은 위에 사이트에 정리 해놓았으니 들어가서 확인 해보면 된다. 그러면 아래 그림에서 색칠한 부분이 구간합중 가장 작은 값이고. 구간합을 출력하면된다.

결과

정리

1.  맨 위, 왼쪽에 흰색일 경우와 검은색일 경우를 배열은 선언하고 비교해서 다른면 1 같은면 0으로 표시를 한다. (행과 열 더해서 짝수이면 같고 홀수이면 다르다.)
2. 탐색이 끝나면 그 배열의 누적합을 구한다.
3. 누적합을 구한 2차원 배열에서 K × K  구간합중 가장 작은 값을 구하고 맨위 왼쪽 흰색인 경우와 검은색인 경우중 작은 작은 값을 출력하면된다.

Code

Python

import sys
input = sys.stdin.readline
sys.maxsize

def minimal_board(color):
    prefix_sum = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if (i + j) % 2 == 0: 
                value = board[i][j] != color
            else:
                value = board[i][j] == color
            prefix_sum[i + 1][j + 1] = prefix_sum[i][j + 1] + prefix_sum[i + 1][j] - prefix_sum[i][j] + value
    
    count = sys.maxsize
    for i in range(1, N - K + 2):
        for j in range(1, M - K + 2):
            count = min(count, prefix_sum[i + K - 1][j + K - 1] - prefix_sum[i + K - 1][j - 1] - prefix_sum[i - 1][j + K - 1] + prefix_sum[i - 1][j - 1])
    return count

N, M, K = map(int, input().split())
board = [list(input()) for _ in range(N)]
print(min(minimal_board('B'), minimal_board('W')))

Java

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

public class Main {

	static int N, M, K;
	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());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		board = new char[N][M];
		String line;
		for(int i = 0; i < N; i++) {
			line = br.readLine();
			for(int j = 0; j < M; j++) {
				board[i][j] = line.charAt(j);
			}
		}
		
		
		System.out.println(Math.min(minimal_board('B'), minimal_board('W')));
		
	}
	
	public static int minimal_board(char color) {
		int count = Integer.MAX_VALUE;
		int value;
		int[][] prefix_sum = new int[N + 1][M + 1];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if((i + j) % 2 == 0) {
					value = board[i][j] != color? 1 : 0;
				}else {
					value = board[i][j] == color? 1 : 0;
				}
				prefix_sum[i + 1][j + 1] = prefix_sum[i][j + 1] + prefix_sum[i + 1][j] - prefix_sum[i][j] + value;
			}
		}
		
		for(int i = 1; i <= N - K + 1; i++) {
			for(int j = 1; j <= M - K + 1; j++) {
				count = Math.min(count, prefix_sum[i + K - 1][j + K - 1] - prefix_sum[i + K - 1][j - 1] - prefix_sum[i - 1][j + K - 1] + prefix_sum[i - 1][j - 1]);
			}
		}
		return count;
	}
				
}