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

문제(https://www.acmicpc.net/problem/1018)

1018번: 체스판 다시 칠하기

 

문제

---

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

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

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

 

입력

---

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

 

출력

---

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

예제 입력 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

---

풀이

 

- 4중 for문을 이용하여 전체 탐색을 진행한다.

 

- 4중 for문이라 복잡도가 매우 높을  거 같지만, 체스판 크기가 8x8로 고정되어 있기 때문에, 시간 복잡도는 O(N*M)

 

- M * N 보드가 주어지면 그 안에서 나눌 수 있는, 8X8 체스판은 (M - 7) * (N - 7) 개이다. 

 

- 검은색, 흰색으로 시작하는 경우가 존재하니 (M - 7) * (N - 7) * 2 가지 경우의 수를 고려해야 한다.

 

- 해당 경우의 수에 대한 정사각형의 수를 구한 뒤 비교를 통해 최소값을 구하면 된다.

 

- 구체적인 과정을 주석을 확인

 

---

코드

package week1;

import java.util.Scanner;

public class Problem7 {
	public class Main{
		
		static char board[][]; // 입력 받을 2차원 배열 보드판.
		static int min = 64; // 최솟값을 찾기 위한 변수. 64인 이유는 8 x 8 체스판을 만들기 위한 최대값이 64이기 때문이다.
		
		
	    public static void main(String[] args){
	      Scanner scan = new Scanner(System.in);
	        
	      int n = scan.nextInt();
	      int m = scan.nextInt();
	      
	      String input;
	      
	      board = new char[n][m];
	      
	      
	      for(int i = 0; i < n; i++) { // 보드판 입력
	    	  input = scan.next();   	  
	    	  for(int j = 0; j<m;j++) {
	    		  board[i][j] = input.charAt(j);
	    	  }
	      }     
	      
	      for(int i = 0; i <= n-8; i++) { // 8 x 8 으로 보드판을 나눈 후 탐색 
	    	  for(int j = 0; j <= m-8; j++) {
	    		 search(i,j); // 8 x 8 크기의 보드판으로 나눈 후 체스판을 만들기 위한 경우의 수를 구하는 메소드
	    	  }
	      }    
	      
	      	System.out.println(min); // 최솟값 출력
	      	
	      	scan.close();
	    }
	    
	    static void search(int x, int y) { 
			int num = 0; //색을 변경한 횟수
			char color = board[x][y]; // 체스판 시작 색을 저장
			
			for(int i = x; i < x + 8; i++) { // 인자의 좌표로 부터 8x8 크기로 탐색
				for(int j = y; j < y + 8; j++) {
					if(board[i][j] != color) { // 체스판의 색과 다르면 바꿔야 하므로 증가.
						num++;
					}
					
	                
					if(color == 'W')  // 체스판의 시작 색이 White이면 다음은 Black이 나와야 하므로 앞으로의 비교를 위해 색을 변경.
						color = 'B';
					else 
						color = 'W';
				}
	            
				if(color == 'W') // 다음 행의 시작 색 역시 변경해 주어야 한다.
					color = 'B';
				else 
					color = 'W';
			}
			
			num = Math.min(num, 64-num); //첫번째 색 기준 black or white 최소값 
		
			min = Math.min(num, min); // 지금까지 구한 min 업데이트
		}
}
}