[백준] 1780 : 종이의 개수 JAVA 풀이

너무 안 풀려서 내가 너무 어렵게 생각하고 있는 건가 하고

다른 분들의 풀이를 검색해보니 어렵게 생각하고 있던 게 맞았다 하하

 

그래서 이 포스트를 참고해서 문제를 해결했다.

https://st-lab.tistory.com/235

[백준] 1780번 : 종이의 개수 - JAVA [자바]

 

대략적인 풀이방법은 이렇다.

보드의 모든 칸을 검사해서 하나의 색으로 구성되어 있다면,

그 색깔의 개수를 1 추가한다.

여러 색이 섞여있다면 그 보드를 9분할하고 다시 그 한 칸이 하나의 색으로 구성돼있는지 검사한다.

 

 

import java.io.*;
import java.util.*;
public class Main{
    // n x n크기의 보드
    public static int[][] board;
    
    public static int GRAY = 0; // -1로만 이루어진 종이의 수
    public static int WHITE = 0; // 0으로만 이루어진 종이의 수
    public static int BLACK = 0; // 1로만 이루어진 종이의 수
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n을 입력받음
        int n = Integer.parseInt(br.readLine());
        
        // 보드의 크기를 n x n으로 설정
        board = new int[n][n];
        StringTokenizer st;
        
        for(int i=0;i<n;i++){
        	// 전체 보드의 한 행을 입력받아서 초기화하는 부분
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<n;j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        partition(0,0,n);
        
        // -1, 0, 1로만 이루어진 종이의 개수를 출력
        System.out.println(GRAY);
        System.out.println(WHITE);
        System.out.println(BLACK);
    }
    public static void partition(int row, int col, int size){
    
    	// 종이가 하나의 값으로만 이루어져 있다면 true
        if(colorCheck(row, col, size)){
        	// 종이가 -1, 0, 1 중 하나로만 이루어져 있다면 그 종이의 개수를 증가시킴
            if(board[row][col] == -1){
                GRAY++;
            }
            else if(board[row][col] == 0){
                WHITE++;
            }
            else{
                BLACK++;
            }
            return;
        }
        
        // 종이가 하나의 색으로만 이루어져 있지 않은 경우
        // 그 종이를 9분할해서 같은 작업을 반복해야 함
        // 따라서 종이의 한 변의 길이를 1/3로 줄임
        int newSize = size/3;
        
        // 9분할한 조각에 대해 같은 작업을 실행함
        partition(row, col, newSize);
        partition(row, col + newSize, newSize);
        partition(row, col + 2*newSize, newSize);
        
        partition(row + newSize, col, newSize);
        partition(row + newSize, col + newSize, newSize);
        partition(row + newSize, col + 2*newSize, newSize);
        
        partition(row + 2 * newSize, col, newSize);
        partition(row + 2 * newSize, col + newSize, newSize);
        partition(row + 2 * newSize, col + 2 * newSize, newSize);
    }
    
    // 종이가 하나의 값으로 이루어져 있는지 확인하는 함수
    public static boolean colorCheck(int row, int col, int size){
    	// 첫 번째 블럭의 값을 color에 저장
        int color = board[row][col];
        
        // 종이가 하나의 값으로만 이루어져있는지 확인
        for(int i=row; i<row+size; i++){
            for(int j=col;j<col+size;j++){
            // 다른 값이 섞여있다면 false를 리턴
                if(color != board[i][j]){
                    return false;
                }
            }
        }
        // 하나의 값으로만 이루어져 있다면 true를 리턴
        return true;
    }
    
}