백준 1018번 : 체스판 다시 칠하기 [JAVA]

문제 링크 : https://www.acmicpc.net/problem/1018

1436번: 영화감독 숌

 

문제 |

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

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

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

 

입력 |

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

 

출력 |

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

 

풀이1 | 메모리 최적화 전

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

public class BOJ1018_20221115 {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	
	static int N, M; // 체스판의 가로, 세로 길이
	static String[][] map; // 체스판 칸 색상을 저장하는 String형 2차원 배열
	
	static int min = 64; // 다시 칠해야 하는 칸의 최소 개수
	
	public static void main(String[] args) throws IOException {
		
		st = new StringTokenizer(br.readLine());
		
		// 체스판의 가로, 세로 길이 입력 받기
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new String[N][M]; // 체스판 객체 생성
		
		for(int row = 0; row < N; row++) {
			map[row] = br.readLine().split(""); // 가로 1줄마다 체스판 칸 색상 입력받기
		}
		
		// 8x8의 크기로 체스판을 잘라낼 것이므로
		// 입력받은 마지막 체스판의 너비로부터 7을 뺀 지점이 마지막 탐색 지점 +1이 된다.
		// 예를 들어, 가로 10 크기의 체스판을 입력받았을 경우
		// 0 ~ 2 지점이 체스판 칸 색상을 검사하는 함수를 실행시킬 시작지점이 된다.
		int startRow = N - 7;
		int startCol = M - 7;
		
		for(int row = 0; row < startRow; row++) {
			for(int col = 0; col < startCol; col++) {
				check(row, col); // 각 탐색 시작 지점을 순회하면서 칸 색상 검사 함수를 실행
			}
		}
		
		System.out.println(min); // 정답 출력
		
	}
	
	private static void check(int row, int col) {
		
		// 체스판을 8x8 크기로 잘라낼 것이므로
		// 마지막 탐색 지점 +1 만큼 종료지점을 설정
		int endRow = row + 8;
		int endCol = col + 8;
		
		// check 함수를 실행시킬 때마다 다시 칠해야하는 칸 색상을 저장하는 count 변수
		int count = 0; 
		
		// 시작 검사 색상은 흰색 "W"로 임의 지정
		String checkColor = "W";
		
		for(int r = row; r < endRow; r++) {
			for(int c = col; c < endCol; c++) {
				
				// 만약 검사 색상과 체스판의 색상이 다를 경우 count 증가
				if(!map[r][c].equals(checkColor)) {
					count++;
				}
				
				// 다음 검사 색상을 반전시켜줌
				if(checkColor.equals("W")) {
					checkColor = "B";
				} else {
					checkColor = "W";
				}
				
			}
			
			// 다음 줄로 넘어갈 때도 검사 색상을 반전시켜줌
			if(checkColor.equals("W")) {
				checkColor = "B";
			} else {
				checkColor = "W";
			}			
		}
		
		// count는 시작 검사 색상을 흰색 "W"으로 했을 경우
		// 64 - count는 시작 검사 색상을 검정색 "B"로 했을 경우
		count = Math.min(count, 64 - count);
		
		min = Math.min(min, count);	// 최소값 업데이트	
	}
	
}

풀이2 | 메모리 최적화 후

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

public class BOJ1018_20221116 {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb;
	
	static int N, M; // 체스판의 가로, 세로 길이
	static int min = 64; // 다시 칠해야 하는 칸의 최소 개수
	
	static boolean[][] map; // 체스판 칸 색상을 저장하는 boolean형 2차원 배열
	
	public static void main(String[] args) throws IOException {
		
		st = new StringTokenizer(br.readLine());
		
		// 체스판의 가로, 세로 길이 입력 받기
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new boolean[N][M]; // 체스판 객체 생성
		
		String inputRow;
		
		for(int i = 0; i < N; i++) {
			
			inputRow = br.readLine(); // 가로 1줄마다 체스판 칸 색상 입력받기
			
			for(int j = 0; j < inputRow.length(); j++) {
				if(inputRow.charAt(j) == 'W') {
					map[i][j] = true; // 만약 흰색이면 true
				} else { 
					map[i][j] = false; // 아니면 false
				}
			}
		}
		
		// 8x8의 크기로 체스판을 잘라낼 것이므로
		// 입력받은 마지막 체스판의 너비로부터 7을 뺀 지점이 마지막 탐색 지점 +1이 된다.
		// 예를 들어, 가로 10 크기의 체스판을 입력받았을 경우
		// 0 ~ 2 지점이 체스판 칸 색상을 검사하는 함수를 실행시킬 시작지점이 된다.
		for(int i = 0; i < N - 7; i++) {
			for(int j = 0; j < M - 7; j++) {
				check(i, j); // 각 탐색 시작 지점을 순회하면서 칸 색상 검사 함수를 실행
			}
		}
		
		System.out.println(min);
		
	}
	
	private static void check(int startRow, int startCol) {
		
		int count = 0; // check 함수를 실행시킬 때마다 다시 칠해야하는 칸 색상을 저장하는 count 변수
		boolean flag = true; // 시작 검사용 boolean 변수는 true로 임의 지정
		
		for(int i = startRow; i < startRow + 8; i++) {
			for(int j = startCol; j < startCol + 8; j++) {
				if(map[i][j] == flag) { // 만약 검사 색상과 체스판의 색상이 같을 경우 count 증가
					count++;
				}
				flag = !flag; // 다음 칸은 다른 색이 나와야하므로 flag를 반전시켜줌
			}
			flag = !flag; // 다음 줄의 첫 칸은 다른 색이 나와야하므로 flag를 반전시켜줌
		}
		
		// 64 - count는 시작 검사 색상을 count로 했을 때와 반대인 경우
		count = Math.min(count, 64 - count);
		
		min = Math.min(min, count); // 최소값 갱신	
	}
	
}

 풀이1과 풀이2 모두 핵심 로직은 동일하다. 하지만 풀이2의 경우에는 체스판의 색상을 저장하는 2차원 배열의 자료형을 boolean형으로 하여 흰색과 검은색의 차이를 참과 거짓으로 나타내 메모리 사용량을 줄였다.

 

 핵심 로직은 문제에서 지민이가 잘라내는 체스판의 크기가 8x8이라는 점이다. 즉 MxN 크기의 체스판에서 8x8크기의 체스판을 이동시키면서 검사한다고 생각하면 문제가 이해하기 쉬울 것이다. 그렇다면 검사의 시작 지점은 어떻게 될까? 당연히 0부터 시작할 것이다. 그렇다면 시작 지점의 마지막 지점은 어디일까? 너비가 M이라면 M까지 시작 지점을 검사하면 될까? 아니다. 체스판은 M까지 밖에 없는데 시작 지점을 M부터 잡는다면 시작 지점 이후부터는 허공을 잘라내려는거나 마찬가지이다.

체스판의 크기가 10x10일 경우

검사 시작지점이 2일 경우 종료지점은 마지막 칸인 9가 된다

 위의 예시 그림처럼 10x10 크기의 체스판을 생각해보자. 잘라내려는 크기가 8x8이므로 0부터 시작하면 7까지, 1부터 시작하면 8까지, 2부터 시작하면 9까지 잘라낼 것이고 3부터는 범위를 초과하게 된다.

 여기서 공식을 만들 수 있는건 "최대 크기 - 7" 지점이 최대 시작 지점이 된다는 것이다. 위의 10x10 크기의 체스판에서는 "9 - 7"(0부터 시작하므로 9가 최대 크기)를 하면 2가 최대 시작 지점이 된다.

 그럼 이제 로직은 간단하다. 모든 시작 지점을 순회하면서 종료 지점까지 알맞은 색상을 검사해 얼마나 많은 칸의 색상을 변경해야하는지 세어서 최소값을 갱신하고 마지막 갱신한 최소값을 결과로 출력하면 된다.

 

 풀이1이 직관적이어서 풀이1을 기준으로 설명하겠다.

		// 체스판의 가로, 세로 길이 입력 받기
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new String[N][M]; // 체스판 객체 생성
		
		for(int row = 0; row < N; row++) {
			map[row] = br.readLine().split(""); // 가로 1줄마다 체스판 칸 색상 입력받기
		}

 문제에서 주어지는 체스판 정보를 입력받는다.

		// 8x8의 크기로 체스판을 잘라낼 것이므로
		// 입력받은 마지막 체스판의 너비로부터 7을 뺀 지점이 마지막 탐색 지점 +1이 된다.
		// 예를 들어, 가로 10 크기의 체스판을 입력받았을 경우
		// 0 ~ 2 지점이 체스판 칸 색상을 검사하는 함수를 실행시킬 시작지점이 된다.
		int startRow = N - 7;
		int startCol = M - 7;
		
		for(int row = 0; row < startRow; row++) {
			for(int col = 0; col < startCol; col++) {
				check(row, col); // 각 탐색 시작 지점을 순회하면서 칸 색상 검사 함수를 실행
			}
		}

 시작 지점을 최대 크기에서 7을 뺀 값으로 지정하고 모든 시작 지점을 검사한다. 검사 로직을 for문 안에 넣으면 너무 복잡해지므로 따로 함수를 만들었다. check 함수에서는 파리미터로 들어간 시작 지점부터 8x8크기의 체스판을 검사해 얼마나 많은 칸의 색상을 변경해야하는지 세고 min 변수에 갱신한다.

	private static void check(int row, int col) {
		
		// 체스판을 8x8 크기로 잘라낼 것이므로
		// 마지막 탐색 지점 +1 만큼 종료지점을 설정
		int endRow = row + 8;
		int endCol = col + 8;
		
		// check 함수를 실행시킬 때마다 다시 칠해야하는 칸 색상을 저장하는 count 변수
		int count = 0;

 8x8 크기의 체스판이므로 종료 지점은 시작 지점으로부터 8을 더한 값으로 지정한다. 그리고 현재 시작 지점에서 얼마나 많은 칸의 색상을 변경하는지 세기 위하여 count 변수를 만든다.

		// 시작 검사 색상은 흰색 "W"로 임의 지정
		String checkColor = "W";
		
		for(int r = row; r < endRow; r++) {
			for(int c = col; c < endCol; c++) {
				
				// 만약 검사 색상과 체스판의 색상이 다를 경우 count 증가
				if(!map[r][c].equals(checkColor)) {
					count++;
				}
				
				// 다음 검사 색상을 반전시켜줌
				if(checkColor.equals("W")) {
					checkColor = "B";
				} else {
					checkColor = "W";
				}
				
			}
			
			// 다음 줄로 넘어갈 때도 검사 색상을 반전시켜줌
			if(checkColor.equals("W")) {
				checkColor = "B";
			} else {
				checkColor = "W";
			}			
		}

 시작 지점의 색상은 임의로 흰색("W")부터 시작한다고 가정한다. 색상이 2가지 밖에 없기 때문에 검은색("B")으로 한다고 해도 크게 문제는 없다.

 시작 지점부터 8x8 크기만큼 순회하면서 만약 검사 색상과 체스판에 칠해져 있는 색상이 다르면 다시 칠해야 하는 칸이므로 count를 증가시킨다. 그리고 다음 칸에는 다른 색상이 와야하므로 검사 색상을 반전시켜준다. 처음에 임의로 흰색("W")으로 했으므로 다음 칸은 검은색("B")이 된다.

 다음 줄로 넘어갈 때도 한 번 더 검사 색상을 반전시켜준다. 첫번째 줄의 첫 칸이 흰색이면 두번째 줄의 첫 칸은 검은색이어야 하기 때문이다. 그런데 "첫번째 줄의 마지막이 검은색이니까 그냥 쓰면 되지 않나요?"라는 의문이 들 수 있는데 이미 다음 칸 검사 색상을 반전시키는 로직이 한 번 들어가있으므로 다시 반전시켜주어야 한다.

		// count는 시작 검사 색상을 흰색 "W"으로 했을 경우
		// 64 - count는 시작 검사 색상을 검정색 "B"로 했을 경우
		count = Math.min(count, 64 - count);
		
		min = Math.min(min, count);	// 최소값 갱신

 체스판을 검사하는 경우는 2가지가 있다. 흰색으로 시작할 경우와 검은색으로 시작할 경우. 지금 이 로직은 흰색으로 시작하는 경우를 보여주고 있는데 검은색으로 시작하는 경우를 위해 다시 동일한 로직을 사용하는 것은 너무 비효율적이다. 잘 생각해보면 흰색으로 시작할 경우와 검은색으로 시작할 경우는 완전히 정반대이다. 만약 흰색으로 시작해서 아무것도 다시 칠할 것이 없는 경우여도 검은색으로 시작해서 검사하면 64(8x8)번 다시 칠해야한다. 그러므로 64에서 count를 뺀 값이 검은색으로 시작해서 칠한 경우라고 할 수 있다.

 

 min은 최소값을 저장하고 있는 전역 변수이다. count는 다음 시작 지점에서 check 함수가 시작될 때 초기화되지만, min 변수는 전역변수이므로 이전의 최소값을 그대로 가지고 있다. 따라서 이전의 최소값과 현재 count 값을 비교하여 최소값을 갱신해준다.

		System.out.println(min); // 정답 출력

 그리고 Main 함수로 다시 돌아와서 모든 시작 지점을 순회하는 for문이 끝난다면 min을 출력해주면 된다.