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

www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

---

• 문제

 

 

 

매우 간단한 문제다!

 

 

※ 주의할 점

1. 어떤 크기로 주어지던, 최소로 칠할 수 있는 8×8 크기를 찾아내야 한다.

 

 

 

 

---

• 알고리즘 [접근 방법]

 

어려운 문제는 아니다.

 

체스판을 만들기 위해서는 한 칸이 상하좌우의 색과 다르면 된다. 또한 체스판이 잘못 칠해져 있는 경우 '최소'의 개수로 칠 할 수 있는 부분을 찾아야 한다.

 

경우의 수는 (가로 칸 개수 - 7) × (세로 칸 개수 - 7) 이다. 그림으로 본다면 대강 아래와 같을 것이다. 최소 크기가 8×8 일 때 경우의 수가 1이기 때문에 각 가로 세로별 길이에 -7 을 해주는 것이다.

 

그리고 경우의 수가 또 있다.

첫 번째 칸이 검은색일 경우와 하얀색일 경우다.

기본적으로 체스판은 상하좌우가 교대로 색이 배치된다. 이 때 첫 칸이 검은색일 경우의 올바르게 색칠하기 위해 변경되어야 할 색들의 개수와 첫 칸이 하얀색일 경우의 올바르게 색칠하기 위해 변경되어야 할 색들의 개수를 비교해야 한다.

 

그렇게 된다면 총 경우의 수는 다음과 같다.

경우의 수 = 2 × (가로 칸 개수 - 7) × (세로 칸 개수 - 7)

 

알고리즘은 기본적으로 W(하얀색) 과 B(검은색)을 구분하기 위해 boolean 2차원 배열을 사용 할 것이다. 그래서 W 일 때는 true, B 일때는 false 로 표현을 할 것이다.

 

그리고 8 × 8 크기의 배열을 하나씩 검사하면서 첫 칸의 색이 하얀색일 경우와 검은색일 경우의 수를 비교하여 칠한 개수의 최솟값을 구하는 것이다.

 

자세한 것은 코드를 보면 바로 이해가 갈 것이다.

 

 

 

 

 

 

 

---

• 2가지 방법을 이용하여 풀이한다.

 

먼저 가장 기본적인 배열을 이용한 방법을 사용할 것이다.

대신 입력을 달리하여 성능의 차이를 같이 볼 수 있도록 두 가지 입력 방법을 쓸 것이다.

 

입력은 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다.

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {

	public static boolean[][] arr;
	public static int min = 64;

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		int M = in.nextInt();

		arr = new boolean[N][M];
		
        
		// 배열 입력 
		for (int i = 0; i < N; i++) {
			String str = in.next();
			
			for (int j = 0; j < M; j++) {
				if (str.charAt(j) == 'W') {
					arr[i][j] = true;		// W일 때는 true 
				} else {
					arr[i][j] = false;		// B일 때는 false
				}

			}
		}

		
		int N_row = N - 7;
		int M_col = M - 7;

		for (int i = 0; i < N_row; i++) {
			for (int j = 0; j < M_col; j++) {
				find(i, j);
			}
		}
		System.out.println(min);
	}

	
	public static void find(int x, int y) {
		int end_x = x + 8;
		int end_y = y + 8;
		int count = 0;

		boolean TF = arr[x][y];	// 첫 번째 칸의 색 

		for (int i = x; i < end_x; i++) {
			for (int j = y; j < end_y; j++) {

				// 올바른 색이 아닐경우 count 1 증가 
				if (arr[i][j] != TF) {	
					count++;
				}
				
				/* 
				 * 다음 칸은 색이 바뀌므로
				 * true라면 false로, false 라면 true 로
				 * 값을 변경한다.
				 */
				TF = (!TF);
			}
			
			TF = !TF;
		}
		
		/*
		 *  첫 번째 칸을 기준으로 할 때의 색칠 할 개수(count)와
		 *  첫 번째 칸의 색의 반대되는 색을 기준으로 할 때의
		 *  색칠 할 개수(64 - count) 중 최솟값을 count 에 저장 
		 */
		count = Math.min(count, 64 - count);
		
		/*
		 * 이전까지의 경우 중 최솟값보다 현재 count 값이
		 * 더 작을 경우 최솟값을 갱신 
		 */
		min = Math.min(min, count);
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

그리고 주석에서도 썼지만, Scanner가 공백, 개행 단위로 자동으로 분리하여 읽어주다보니 생기는 문제가 있다.

nextLine() 의 경우 '개행(줄바꿈)'을 기준으로 한 줄을 통째로 읽는데, nextInt() 같은 메소드는 '공백' 이나 '개행'이 입력되면 그 전까지 읽힌 입력된 문자열을 int형으로 변환되어 메모리에 올라가고, 개행은 '스트림'에 계속 남아있게 된다.

그렇기 때문에 공백단위로 입력받았다가 개행으로 입력받기 시작할 때, nextLine() 을 쓰면, 이전에 스트림에 남아있던 개행(줄바꿈)이 저장되어 버린다.

 

그래서 한 번 줄바꿈입력을 통해 이러한 일을 방지할 수 있도록 한다.

나머지는 주석으로 모두 설명했으니 읽어보면서 참고하면 될 것 같다.

 

---

- 방법 2 

 

 

Scanner 대신 BufferedReader 을 사용한 방법이다.

알고리즘 자체는 그대로 똑같다.

 

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

public class Main {

	public static boolean[][] arr;
	public static int min = 64;

	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());

		arr = new boolean[N][M];
		

		// 배열 입력 
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			
			for (int j = 0; j < M; j++) {
				if (str.charAt(j) == 'W') {
					arr[i][j] = true;		// W일 때는 true 
				} else {
					arr[i][j] = false;		// B일 때는 false
				}

			}
		}

		
		int N_row = N - 7;
		int M_col = M - 7;

		for (int i = 0; i < N_row; i++) {
			for (int j = 0; j < M_col; j++) {
				find(i, j);
			}
		}
		System.out.println(min);
	}

	
	public static void find(int x, int y) {
		int end_x = x + 8;
		int end_y = y + 8;
		int count = 0;

		boolean TF = arr[x][y];	// 첫 번째 칸의 색 

		for (int i = x; i < end_x; i++) {
			for (int j = y; j < end_y; j++) {

				// 올바른 색이 아닐경우 count 1 증가 
				if (arr[i][j] != TF) {	
					count++;
				}
				
				/* 
				 * 다음 칸은 색이 바뀌므로
				 * true라면 false로, false 라면 true 로
				 * 값을 변경한다.
				 */
				TF = (!TF);
			}
			
			TF = !TF;
		}
		
		/*
		 *  첫 번째 칸을 기준으로 할 때의 색칠 할 개수(count)와
		 *  첫 번째 칸의 색의 반대되는 색을 기준으로 할 때의
		 *  색칠 할 개수(64 - count) 중 최솟값을 count 에 저장 
		 */
		count = Math.min(count, 64 - count);
		
		/*
		 * 이전까지의 경우 중 최솟값보다 현재 count 값이
		 * 더 작을 경우 최솟값을 갱신 
		 */
		min = Math.min(min, count);
	}
}

 

 

 

역시 필자는 Scanner 보다 BufferedReader 가 더 편한 것 같다.

아예 한 줄로 읽을 수 있게 통일되어 있다보니 Scanner 처럼 자칫 에러상황이 날 경우가 더 적어진다.

(단순한게 역시 최고다...)

 

 

 

 

 

 

 

---

• 성능

 

위에서 부터 순서대로

 

채점 번호 : 20032665  -  BufferedReader

채점 번호 : 20032492  -  Scanner

 

 

입력의 경우 확실히 Scanner 보다는 BufferedReader 가 빠르고 좋다.

 

---

• 정리

 

이번 문제도 그렇게 어려운 문제는 아니였다.

다만 필자가 정답률이 왜이렇게 낮은지 찾아보니까, 검사하려는 8×8 배열에서 첫번째 칸이 하얀색일 때와 검은색일 때, 두 경우의 수를 미처 생각하지 못해 틀린 경우가 가장 많은 것 같았다.

 

문제는 역시 꼼꼼히 읽고 정리한 뒤 풀어보는 습관을 갖는게 중요한 듯 하다.