[Solved]/BOJ

[백준 2630] 색종이 만들기

응파카 2023. 5. 14. 23:27

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

 

2630번: 색종이 만들기

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

www.acmicpc.net

두 개의 2차원 배열 board 와 check 를 만들어 보자,

if 종이 전체가 같은 색깔로 칠해져 있지 않다면
    - 가로와 세로 중간을 잘라서 4등분 한다.
        - 이를 반복
단일 색상의 색종이 수를 색상별로 출력하면 되는 문제이다

즉, 다음 과정을 반복한다

1. 영역의 전체 색상이 같은지 확인한다
    if 같으면 해당 색상 count++
    else 4등분하여 각 부분별로 문제 해결

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int blueCount = 0;
    static int whiteCount = 0;

    static int[][] board;

    static boolean checkColor(int xFrom, int xTo, int yFrom, int yTo){
        int first = board[xFrom][yFrom];
        for(int i=xFrom; i<=xTo; i++){
            for(int j=yFrom; j<=yTo; j++){
                if(board[i][j] != first) return false;
            }
        }
        return true;
    }

    static void DC(int xFrom, int xTo, int yFrom, int yTo){
        if(checkColor(xFrom, xTo, yFrom, yTo)){
            if(board[xFrom][yFrom] == 0){
                whiteCount++;
            }else{
                blueCount++;
            }
        }else{
            DC(xFrom, (xTo+xFrom)/2, yFrom, (yTo+yFrom)/2);
            DC(xFrom, (xTo+xFrom)/2, (yTo+yFrom)/2+1, yTo);
            DC((xTo+xFrom)/2+1, xTo, yFrom, (yTo+yFrom)/2);
            DC((xTo+xFrom)/2+1, xTo, (yTo+yFrom)/2+1, yTo);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str;
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];

        for(int i=0; i<N; i++){
            str = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                board[i][j] = Integer.parseInt(str.nextToken());
            }
        }

        DC(0, N-1, 0, N-1);

        System.out.println(whiteCount);
        System.out.println(blueCount);
    }
}

'[Solved] > BOJ' 카테고리의 다른 글

[백준 1106] 호텔  (0) 2023.05.17
[백준 14600] 샤워실 바닥 깔기 (Small)  (0) 2023.05.16
[백준 2448] 별 찍기 - 11  (0) 2023.05.13
[백준 1074] Z  (0) 2023.05.12
[백준 17136] 외판원 순회  (0) 2023.05.07