[백준] 체스판 다시 칠하기 (1018)(java)

원본 문제 : https://www.acmicpc.net/submit/1018/13163725

 

문제

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

하지만 지민이는 이 보드가 체스판처럼 검정/흰색 패턴이 번갈아가며 색칠해져있지 않기 때문에 고민에 빠졌다. 따라서 지민이는 8*8크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야 겠다고 생각했다. 당연히 8*8크기는 아무데서나 골라도 된다.

현재 보드의 색이 어떤지 상태가 주어질 때, 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 구하는 프로그램을 작성하시오.

체스판은 각 정사각형이 검정 또는 흰색이며, 변을 공유하는 두 개의 사각형이 같은 색이 아닐 때 이다. 따라서 위 정의에 의하면 체스판의 색은 항상 두 가지가 가능한데, 하나는 왼쪽 위 코너가 흰색인 것, 검정색인 것 두가지이다.

입력

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

출력

첫째 줄에 지민이가 8*8크기로 자른 뒤에 다시 칠해야하는 정사각형 개수의 최솟값을 출력한다.

예제 입력 1

8 8

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBBBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

예제 출력 1

1

예제 입력 2

10 13

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

BBBBBBBBWBWBW

BBBBBBBBBWBWB

WWWWWWWWWWBWB

WWWWWWWWWWBWB

예제 출력 2

12

 

 

 

 

 

처음엔 배열의 8x8을 잘라서 그냥 비교하면 되는 줄 알았다.

B로 시작하는 8x8 배열과, W로 시작하는 8x8 배열을 생성하여

입력 받은 배열 값을 두 배열과 비교해 다르면 카운트 하는 방식으로

Math.min함수로 최솟값만 남게 했다.

 

예제 1은 성공했지만 예제2에서 틀렸다하여 문제를 다시보니

입력 받은 배열을 8X8배열로 잘랐을때

(기준이 [0][0]만 있는 것이 아니라 입력 받은 배열을 모든 경우 수의 8x8로 잘랐을때 최솟값)

최솟값을 찾아내는 것이었다.

 

 

문제 풀이 1

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		final int ROW = sc.nextInt();
		final int COL = sc.nextInt();
		
		String[] bw = new String[ROW];
		String[] wb = new String[ROW];
		
		for(int i = 0; i < ROW; i++) {
			bw[i]="";
			wb[i]="";
			for(int j = 0; j < COL; j++) {
				if(i%2==0&&j%2==0) {
					bw[i] += "B";
					wb[i] += "W";
				}
				if(i%2==0&&j%2==1) {
					bw[i] += "W";
					wb[i] += "B";
				}
				if(i%2==1&&j%2==0) {
					bw[i] += "W";
					wb[i] += "B";
				}
				if(i%2==1&&j%2==1) {
					bw[i] += "B";
					wb[i] += "W";
				}
			}
		}
		
		String[] strArr = new String[ROW];
		for(int i = 0; i < ROW ; i++)
			strArr[i] = sc.next();
		
		int countW=0, countB=0, min=ROW*COL;
		int iShift = 0, jShift = 0;
		while(true) {
			if(iShift+8>ROW) break;
			int idx = 0;
			for(int i = iShift ; i < 8+iShift; i++) {
				int jdx = 0;
				for(int j = jShift; j < 8+jShift; j++) {
					if(bw[idx].charAt(jdx)!=strArr[i].charAt(j))
						countW++;
					if(wb[idx].charAt(jdx)!=strArr[i].charAt(j))
						countB++;
					jdx++;
				}
				idx++;
			}
			min = Math.min(min, countW);
			min = Math.min(min, countB);
			countA = countB = 0;
			
			if(iShift+8<=ROW) {
				if(jShift+8<COL) {
					jShift++;
				}
				else {
					iShift++;
					jShift=0;
				}
			}
		}
		
		System.out.println(min);

	}
}

 

 

 

문제 풀이2

일부를 함수화하여 코드를 조금 더 간결하게 줄이고,

비교할 8x8의 두 배열을 컴파일 할때 마다 생성하지 않고 static 변수로 지정하여

메모리 사용량과 시간을 절약했다.

import java.util.Scanner;

public class Main {
	static String[] wb = {"WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW"};
	static String[] bw = {"BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB"}; 

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		final int ROW = sc.nextInt();	//ROW를 입력 받음
		final int COL = sc.nextInt();	//COLUMN을 입력 받음

		String[] strArr = new String[ROW];
		for(int i = 0; i < ROW ; i++)
			strArr[i] = sc.next();		//ROW만큼의 문자열을 입력 받음
		
		int min=ROW*COL;	//최댓값지정
		int iShift = 0, jShift = 0;		//오른쪽, 아래쪽 시프트할 변수의 선언 및 초기화
		while(true) {
			if(iShift+8>ROW) break;		//아래쪽으로 시프트해서 8x8배열을 더 탐색할 수 없을 경우 break;
			
			min = Math.min(min, checkBW(strArr, iShift, jShift));
			
			if(iShift+8<=ROW) {			//아래쪽으로 시프트해서 탐색할 수 있는 경우
				if(jShift+8<COL) jShift++;	//오른쪽으로 시프트해서 더 탐색할 수 있는 경우, 오른쪽으로 한 칸 시프트
				else { iShift++; jShift=0;}	//오른쪽으로 시프트해서 더 탐색할 수 없는 경우, 아래쪽으로 한 칸 시프트
			}								// 및 왼쪽 시프트 값을 0으로 초기화
		}
		System.out.println(min);
	}
	
	public static int checkBW(String[] strArr, int iShift, int jShift) {
		int countW = 0;			//W를 교체해야 하는 경우 카운트 값
		int countB = 0;			//B를 교체해야 하는 경우 카운트 값
		
		for(int i = iShift ; i < 8+iShift; i++) {		//아래쪽으로 시프트된 값부터 탐색을 시작
			for(int j = jShift; j < 8+jShift; j++) {	//오른쪽으로 시프트된 값부터 탐색을 시작
				if(bw[i-iShift].charAt(j-jShift)!=strArr[i].charAt(j))
					countW++;
				if(wb[i-iShift].charAt(j-jShift)!=strArr[i].charAt(j))
					countB++;
			}
		}
		return Math.min(countW, countB);				//두 값을 비교하여 최솟값 리턴
	}
}