[백준,BOJ 1018] 체스판 다시 칠하기(JAVA 구현, 재풀이)

-내 생각

  저번에 풀 때도 어려워서 제대로 풀지 못했던 경험이 있는 문제다. 다시 풀기 위해 이전에 풀었던 풀이를 보았는데, 너무 복잡하다고 생각이 들어서 더 간단하게 푸는 방법이 없을까 생각하며 다른 블로거분들이 작성한 풀이를 참고해보았는데, 아래의 블로그에서 잘 설명하고 있다고 생각해서 따로 링크를 남겨둔다. 방문해서 참고하면 도움이 될 것 같다.

 

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

-해법

import java.util.Scanner;

public class Main{
	
	static char arr[][]; // 입력받을 체스판이 저장 될 2차원 배열
	static int min = 64; // 최솟값을 찾기 위한 변수, 8x8 크기의 체스판에서 바꿔야 하는 최댓값은 64번 모두 바꾸는 경우이기에 64로 초기화
	
	static void check(int x, int y) { // 8x8 크기의 체스판에서 바꿔야 하는 경우의 수를 체크하는 메소드
		int cnt = 0;
		char color = arr[x][y]; // 전달받은 좌표의 좌상단 체스 색을 저장
		
		for(int i=x;i<x+8;i++) { // 전달받은 좌표에서 8x8 크기로 탐색
			for(int j=y;j<y+8;j++) {
				if(arr[i][j] != color) { // 체스판의 시작 색과 다르면 바꿔야 하므로 증가.
					cnt++;
				}
				
                // 체스판의 시작 색이 W이면 다음은 B가 나와야 하므로 비교를 위해 값을 변경 반대의 경우도 마찬가지
				if(color == 'W') color = 'B';
				else color = 'W';
			}
            // 다음 행의 시작 역시 바꾸어 주어야 한다.
			if(color == 'W') color = 'B';
			else color = 'W';
		}
		
        // cnt는 한 색의 변경 횟수, 64- cnt는 반대 색의 변경 횟수이다.
		cnt = Math.min(cnt, 64-cnt);
		
        // 여지껏 구한 min과 비교
		min = Math.min(cnt, min);
	}
	
    public static void main(String[] args){
      Scanner in = new Scanner(System.in);
        
      int n = in.nextInt();
      int m = in.nextInt();
      
      arr = new char[n][m];
      
      String input;
      
      for(int i=0;i<n;i++) { // 체스판 입력
    	  input = in.next();   	  
    	  for(int j=0;j<m;j++) {
    		  arr[i][j] = input.charAt(j);
    	  }
      }     
      
      for(int i=0;i<=n-8;i++) { // 체스판이 8x8크기 이상일 경우 자를 수 있는 범위의 좌표를 메소드에 전달 	    
    	  for(int j=0;j<=m-8;j++) {
    		 check(i,j);
    	  }
      }    
      
      	System.out.println(min); // 최솟값 출력
      	
      	in.close();
    }
}

  처음에 풀었던 방식과 다르게 수학적으로 풀었던 문제라고 생각한다. 우선 동작 과정은 아래와 같다.

 

  1. 체스판의 입력, 입력이 공백없이 이루어지기 때문에 문자열로 받은 후, charAt() 메서드를 활용해 입력받는다.

  2. 8x8 크기로 자를 수 있는 좌표의 범위로 탐색 ( 체스판의 시작점, 좌상단을 의미하며 8x8 크기이기 때문에 전체 체스판 크기에서 -8을 해주면 8x8크기로 자를 수 있는 모든 경우의 수이다.)

  3. 별도의 메소드로 위에서 반복되는 좌표를 인자로 전달.

  4. 메소드에서 전달받은 좌표는 8x8크기로 자른 체스판에서 좌상단, 즉 첫 색이 되므로 color에 해당 값을 저장

  5. 시작 좌표 x, y로 시작하고 +8까지 반복하여 8x8크기의 체스판을 탐색

  6. 좌상단부터 우하단으로 가면서 체스판 색을 비교, 다르면 cnt가 증가 (단, 한 번 비교한 색 다음에는 반대색이 나오므로 변경해준다.)

  7. 다음 행으로 이동할 때 역시 첫 번째 색과 반대가 돼야 하므로, 한 번 더 바꾸어 다음 반복 실행.

  8. 이렇게 구한 cnt는 첫 번째 색을 기준으로 바꾸어야 할 색의 수, 반대색의 수는 반대로 생각하면 64개의 체스 색 중 cnt개만큼 맞게 칠해져 있는 것이므로 고쳐야 하는 수는 64-cnt가 된다.

(ex. 예제 입력 1에서 첫 번째 색이 W로 비교 시 바꾸어야 할 색은 1개이다. 그러나 첫 번째 색이 B로 비교 시 바꾸어야 할 수는 앞선 1개를 제외하고 63개이다.) 

  9. W와 B의 경우에서 최솟값을 Math.min() 메서드로 구한다.

  10. 마지막으로 가능한 8x8 크기의 체스판 경우에서의 최솟값 역시 Math.min()으로 구한다.

 

이와 같은 동작과정을 알고, 위에 언급한 다른 분의 블로그에 설명되어 있는 글을 읽는다면 충분히 이해할 수 있을 것이라 생각이 든다.