[백준] 1018번 체스판 다시 칠하기 JAVA (자바) 풀이

문제 1018 

M x N 크기 보드 (검정색 & 흰색)

보드를 잘라서 8 x 8 크기의 체스판으로 만들기

체스판 규칙 : 검적생 흰색 번갈아서 칠할 것

 

잘라낸 보드 판을 체스판 규칙에 맞게 다시 칠해야 하는 최소 횟수를 구하시오

 

 

[입력]

 

 :  첫째 줄에 N과 M ( 8보다 크거나 같고 50보다 작거나 같은 자연수)

 :  둘째 줄부터 N개의 줄 보드 각 행의 색이 주어진다 ( B = 검은색, W = 흰색 )

 

 

 [출력]

 :  다시 칠해야 하는정사각형 개수

 

     

 

 

 [참고]

 

1. 맨 처음 시작 판을 기준으로 번갈아 색을 칠할 것!

 

• 첫 시작판을 한가지 색으로 고정하자!
  흰색판일 경우로만 진행하는 것 
  흑과 백 경우의 수가 2개 이므로 boolean을 사용!
  (0과 1로 사용해도 괜찮다)
  
  
• 반대색은 무조건 64 - (count)
  위에서 흰색판일 경우로 진행했다 = count 라고 할 때
  반대색인 검정판으로 시작할 경우의 색칠 수는 흰색판 기준 색칠 수의 반대
  => 64(전체 판 개수) - count 해주기
  
  
• result = Integer.MAX_VALUE;
  초기 비교 경우 result를 가장 낮은 0으로 초기화 한다면 min 값을 구할 때 계속해서 0에 머문다
  초기 비교를 위해 가장 높은 값으로 초기화 한다
  
• 자릿수가 2개 뿐이라 어차피 비교 대상은 하나이기 때문에 일정한 공차를 가진다
  ex) 16 ▶ 한수 ( 공차 = 5 ), 98 ▶ 한수 ( 공차 = -1 )

 

2. 백의 자리 숫자부터 계산할 것

 

• 100의 자리라면?
  
  - 공차 범위: - 4 ~ 4
  
  - 범위가 1000까지인데 1000은 한수가 아니므로 111 ~ 999까지 검사하면 된다

 

 [코드]

 

import java.util.*;
import java.io.*;
public class Main{
    static boolean board[][]; 
    static int result =Integer.MAX_VALUE;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        board = new boolean[N][M];
        
        for(int i=0; i<N; i++){ // 행
            String str = br.readLine();
            for(int j=0; j<M; j++){ //열
                board[i][j]=(str.charAt(j)=='W');
            }
        }
        
        //체스판 만들기
        for(int i =0; i<=N-8; i++){
            for(int j=0; j<=M-8;j++){
                result = Math.min(count(i,j), result);
            }
        }
        
        System.out.println(result);
    }
    
    public static int count(int x, int y){
       
        int count = 0; 
        boolean color = board[x][y];
        
        for(int i =x; i <x+8; i++){
            for(int j =y; j<y+8; j++){
                if(board[i][j]!=color){
                    count++;
                }
                color = !color;
            }
            color = !color;
        }
        
        return Math.min(count, 64-count);
    }
}

 

 

 [해설]
     

 :  static boolean board[][]; 
    static int result =Integer.MAX_VALUE;  result 최대로 초기화

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
        
 :  st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());  가로 길이
    int M = Integer.parseInt(st.nextToken());  세로 길이
    board = new boolean[N][M];  흑과 백 간편한 비교를 위해 boolean 설정
        
 :  for(int i=0; i<N; i++){  행마다 검사
           String str = br.readLine();  문자라서 좋은 점 한줄씩 통으로 볼 수 있다
           for(int j=0; j<M; j++){  열마다 검사
                board[i][j]=(str.charAt(j)=='W');  char로 문자 하나씩 뜯어보고 W라면 true 지정
           }
    }
        
 :  for(int i =0; i<=N-8; i++){  가로 시작점 limit
           for(int j=0; j<=M-8;j++){  세로 시작점 limit
                result = Math.min(count(i,j), result);  result랑 count 돌린 것 중에 최소값
           }
    }
        
 :  System.out.println(result);  출력
        
 

 :  public static int count(int x, int y){
       
        int count = 0;  색칠횟수 초기화
        boolean color = board[x][y];  기준 컬러 정하기 ( = 첫 시작판 컬러 )
        
        for(int i =x; i <x+8; i++){  체스판 가로길이 8
            for(int j =y; j<y+8; j++){  체스판 세로길이 8
                if(board[i][j]!=color){  기준 컬러랑 다르면 색칠
                    count++;
                }
                color = !color;  판을 하나씩 옮겨갈 때마다 기준 컬러 바꿔주기 (열이동)
            }
            color = !color;  판이 다음 줄로 넘어갈 때마다 기준 컬러 바꿔주기 (행이동)
        }
        return Math.min(count, 64-count);  맨처음 정한 기준컬러와 기준컬러의 반대의 경우 색칠 수 비교
    }
}
    
 

 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기