백준 1018 <체스판 다시 칠하기>

1018번: 체스판 다시 칠하기 (acmicpc.net)

1018번: 체스판 다시 칠하기

이해하기는 쉬운 문제였다만 코드로 구현하기 어려웠다.

 

*문제파악

문제의 첫 조건

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

>> MxN 즉 , 이 전체의 틀은 직사각형일수도 있고 정사각형일 수도 있지만 이들을 8x8 짜리 정사각형으로 강제로 만들어서 이상적인 체스판을 구현해야함.

 

2. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다  >>여기서 이상적인 체스판의 힌트. (물론 상식이긴한데) 첫번째 배경이 검정인 경우 or 하얀색인 경우오직 2

 

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

 

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

즉. 뒤죽박죽 사각형에서 이상적인 8x8 체스판 정사각형을 만들기 위한 최소의 색깔 바꾸는 횟수를 구하라.

문제 이해는 쉽다. 다만 이걸 어떻게 코드로 구현해야할까.

 

 

* 해설시작..어려운 포인트는 전체적으로 NxM짜리의 사각형에서 8x8를 추출해야하는데, 여기서 이 전체 사각형의 형태가 예를들어BWBWBBBBBWBWB
BWBWBWBWBWBBB
BWBWBWBWBWBWB이런식으로 나온다고 가정했을때 여기서 8x8를 임의 추출하는 것.. 여기서 멘붕이온다이걸 다 뒤져아하나? 1번생각 뒤진다고해서 어케 최소를 갖고올까?

 

조금 스마트하게 가자면 전체 사각형 중 8x8 area가 나올수있는 경우의 수는 그렇게 많지않다.

예를들어 사각형이 9x8형태라고 가정한다면 총 2개가 나오겠다. 1번째행으로 시작하는 사각형 1개와 2번째행으로 시작하는 사각형 1개.

일반화 시켜보면 (n-7)x(m-7)개가 전체 중 8x8짜리 정사각형이 들어갈수있는 경우이다.

 

자 그렇다면 저 경우의 수들 중 첫째행과 첫째열을 기점으로 8x8짜리 이중 for문을 돌며, 이상적인 체스판을 위해 바뀌어야하는 색깔을 최소를 구하려면, 

1. ArrayList와 같은 걸로 count된 색칧수를 모아서 min때리거나

2. 애초에 클래스 객체로 min을 만들어서 keep 최신화하던가

이건 취향차이겠다.

 

 

 

여기서 point는 이상적인 체스판이 되기 위해 각각 이중 for문을 돌것이다. 

하지만 첫 색깔의 비교를 하양 or 검정으로 비교할텐데, 이때를 catch하는게 어렵다

이상적인 체스판의 갯수는 두개다. 하양시작하는거 , 검정시작하는거

8x8짜리 임의로 끄집어낸 녀석이 둘중에 어떤 이상적인 체스판으로 될때 최소한의 색깔을 칠할지는 아무도 모르기에 두개 다 비교를 해줘야한다.. 여기가 젤 어렵다. 

이정도 설명이면 코드가 이해될것이다.!

import java.util.*;
public class Main {
	//클래스 변수
	public static int min =  64; //이 값이 바꿔야할수의  가장 최대의 값이 되겠다. 8x8에세
	public static boolean[][] arr;
	

	public static void main(String[] args) {
		//8x8짜리로 최종적으로 만들어야함
		Scanner sc = new Scanner(System.in);
		ArrayList<String> whole = new ArrayList<String>();
		
		
		int 행 = sc.nextInt();
		int 열 = sc.nextInt();
		
		arr = new boolean[행][열];
		
		for(int i=0; i<행; i++) {
			String str = sc.next();
			for(int j=0; j<열; j++) {
				//하양칸일떈 true
				if(str.charAt(j) == 'W') {
					arr[i][j] = true;
				}
				//검정칸일땐 false
				else {
					arr[i][j] = false;	
				}
			}
		}
		
		int 검사해야할행 = 행-7;
		int 검사해야할열 = 열-7;
		
		for(int i=0; i<검사해야할행; i++) {
			for(int j=0; j<검사해야할열; j++) {
				find(i,j);
			}
		}
		
		
		System.out.println(min);
		//메인 method ends.
	}
	public static void find(int x, int y) {
		int 검사끝행 = x+8;
		int 검사끝열 = y+8;
		int 바꿔야할색 = 0;
		boolean 첫번째색= arr[x][y];
		for(int i=x; i<검사끝행; i++) {
			for(int j=y; j<검사끝열; j++) {
				if(arr[i][j] != 첫번째색) {
					바꿔야할색++;
				}
				첫번째색 = !첫번째색; //계속 바꿔줘야한다. 이 for문은 8번 돌기에 첫번째색은 8번 바뀐다
								 //처음 색이 B였다면 B W B W B W B W B 하지만 다음칸에는  W B W B 이 순서로 비교를 해줘야함 . 즉 다음줄 넘어갈때의 첫 색은 W여야함.
								 //근데 처음색이 B로 되어있기 때문에 
				
			}
			첫번째색 = !첫번째색; // 다음 for문으로 넘어갈때 색깔을 바꿔주어 비교를 해야함.
			
			
		}
		//for문 ends.	
		
		바꿔야할색 = Math.min(바꿔야할색, 64-바꿔야할색); //BWBWBWBW로 시작하는 이상적인 체스판으로 되기 위해 바뀌어야할색
												//WBWBWBWB로 시작하는 이상적인 체스판으로 되기 위해 바뀌어할색은 x, 64-x이겠다.
													//위 for문에서는 첫번째 인덱스인 첫번째색으로 시작하는 이상적인 체스판을 골라서 그렇다.
		
		min = Math.min(min, 바꿔야할색); //바꿔야할색의 최소를 초기화 시켜준다
		//메소드가 두개이기에 전체 클래스 객체인 min과 arr을 써서 find()와 main() 둘다 들락날락 거리게 할수 있게 ..
		
	}

}