[백준] 단계별로 풀어보기(단계:18, 누적합,JAVA)25682번, 체스판 다시 칠하기 2

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

누적합?

입력되는 값들의 누적합 값을 따로 저장하여 필요에 따라 사용하는 알고리즘입니다.

 

예를 들어 1 5 4 36 8이 입력되었을 때 누적합 값을 저장한 배열을 표로 표현하면

	1	5	4	36	8
누적합	1	6	10	46	54

 

이 문제에 핵심은

1. M×N 사각형 보드에서 K×K 정사각형으로 잘랐을 때 체스판의 보드가 되어야 합니다.

2. 보드를 잘랐을 때 체스판이 되도록 색칠할 수 있습니다.

3. 체스판은 첫 칸의 색에 따른 2가지 경우가 존재합니다.

4. 색칠하는 횟수가 가장 작은 횟수를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 누적합을 구성한 뒤 체스판을 K×K으로 자르는 모든 경우를 탐색합니다.

 

3. 색을 칠한 최소 횟수를 결과로 출력합니다.

 

체스판의 2가지 경우.

 

첫 칸에 따라 2가지 경우로 나뉠 수 있습니다.

 

흰색

W	B	W
B	W	B
W	B	W

검은색

B	W	B
W	B	W
B	W	B

색을 칠해야 하는 경우를 배열로 표현하면 서로 반대되는 것을 확인할 수 있습니다.

 

예를 들어 아래와 같은 M×N보드가 존재할 때

W	W	W
B	B	B
W	B	W

흰색(0 : 색칠 X, 1 : 색칠 O)

0	1	0
0	1	0
0	0	0

검은색(0 : 색칠 X, 1 : 색칠 O)

1	0	1
1	0	1
1	1	1

 

체크판의 경우가 2개이기 때문에 두 경우에서 색칠의 최소값을 구해야합니다.

2가지 경우를 모두 확인하는 것보다는 서로 칠하는 경우가 반대가 되는 것을 응용합니다.

 

예를 들어 

흰색에 대해서 칠하는 경우의 최소, 최대 횟수를 구한 뒤

K×K - 최대 횟수 : 검은색의 최소 횟수

 

2차원 배열 누적합.

 

1	2	3
4	5	6
7	8	9

행 더하기

1	3	6
4	9	15
7	15	24

열 더하기

1	3	6
5	12	21
12	27	45

45(2, 2) : 1 ~ 9의 합

21(2, 1) : 1 ~ 6의 합

....

 

예제입력1.

 

1. 입력된 정보를 저장합니다.

 

N : 4

M : 4

K : 3

B	B	B	B
B	B	B	B
B	B	B	W
B	B	W	B

 

 

 

2. 누적합을 구성한 뒤 체스판을 K×K으로 자르는 모든 경우를 탐색합니다.

※저는 체스판의 첫 색을 검은색이 되는 것을 기준으로 구하였습니다.

 

검은색(0 : 색칠X, 1 : 색칠O)

0	1	0	1
1	0	1	0
0	1	0	0
1	0	0	0

 

누적합 구성.

행 더하기.

0	1	1	2
1	1	2	2
0	1	1	1
1	1	1	1

열 더하기.

0	1	1	2
1	2	3	4
1	3	4	5
2	4	5	6

※3×3(K = 3)으로 자르는 모든 경우 중 1가지 경우를 보여드리겠습니다.

0	1	1	2
1	2	3	4
1	3	4	5
2	4	5	6

전체의 합(6) - 자른 보드의 상단 합(2) - 자른 보드 왼쪽 합(2 - 0) = 2

[i][j]는 자른 부분의 누적합의 위치

점화식으로 표현 : board[i][j] - (board[i-K][j] + board[i][j-K] - board[i-K][j-K])

위의 경우

i = 4, j = 4

board[4][4] - (board[1][4] + board[4][1] - board[1][1])

6 - (2 + 2 - 0) = 2

 

3. 색을 칠한 최소 횟수를 결과로 출력합니다.

첫 칸이 검은색일 때 색을 칠하는 최대값 : 4, 최소 : 2

첫 칸이 흰색일 때 색을 칠하는 최소값 : K×K - 최대값 = 3×3 - 4 = 5

 

최소값 2를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 N,M,K를 띄어쓰기 끼준 나누어 저장합니다.
• M×N 보드에서 첫 칸이 검은색으로 시작할 때 색칠 관련 정보를 저장합니다.
• 누적합을 구하기 위해서 행, 열 더하기를 진행합니다.
• K×K로 자르는 모든 경우에서 점화식을 이용하여 최대값과 최소값을 구합니다.
• 최소값과 최대값을 이용하여 시작칸이 검은색, 흰색일 때의 최소값을 비교합니다.
• 색칠하는 최소 횟수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다. 

 

결과 코드

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


public class Main {
    static int N, M, K, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static int[][] board;	//M×N배열에 색칠 관련 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        board = new int[N+1][M+1];
        //false : 검은색, true : 흰색
        //첫 칸은 검은색으로 설정.
        boolean color = false;	
        //첫 칸이 검은색일 때 칠하는 경우 저장
        for(int i=1;i<=N;i++){
            String str = br.readLine();
            for(int j=1;j<=M;j++){
                char c = str.charAt(j-1);
                if(!color && c == 'W')	//검은색으로 색 변경
                    board[i][j] = 1;
                else if(color && c == 'B')	//흰색으로 색 변경
                    board[i][j] = 1;
                color = !color;
            }
            if(M % 2 == 0)
                color = !color;
        }
        //누적합, 행 더하기.
        for(int i=1;i<=N;i++){
            int temp = board[i][1];
            for(int j=2;j<=M;j++){
                temp += board[i][j];
                board[i][j] = temp;
            }
        }
        //누적합, 열 더하기.
        for(int i=1;i<=M;i++){
            int temp = board[1][i];
            for(int j=2;j<=N;j++){
                temp += board[j][i];
                board[j][i] = temp;
            }
        }
        //K×K 정사각형 자르는 모든 경우 탐색
        for(int i=K;i<=N;i++){
            for(int j=K;j<=M;j++){
                //점화식을 이용한 해당 합 구하기
                int temp = board[i][j] - (board[i-K][j] + board[i][j-K] - board[i-K][j-K]);
                min = Math.min(min, temp);	//최소값 비교하기
                max = Math.max(max, temp);	//최대값 비교하기
            }
        }
        //시작이 검은색일 때 : min
        //시작이 흰색일 때 : K*K - max
        int answer = Math.min(min, K*K - max);	//최소 횟수 구하기
        bw.write(answer + "");	//최소 횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}