본문 바로가기

Java/백준

[JAVA] 백준 2630 색종이 만들기

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

 

2630번: 색종이 만들기

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

www.acmicpc.net

 

- 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 

 

- 전체 종이의 크기가 N*N(N=2^k, k는 1이상 7이하의 자연수)이라면 종이를 자르는 규칙은 다음과 같다, 

 

- 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 아래 그림과 같이 똑같은 크기의 네 개의 N/2*N/2 색종이로 나눈다. 

- 나누어진 종이 1,2,3,4 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다.

- 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다. 

 

 

 

 

 

- 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램 

 

- N = 전체 종이의 한 변의 길이, N은 2,4,8,16,32,64,128 중 하나

- 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어짐 

 

 

 

문제 풀이 

 

분할 정복 알고리즘 

- 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 

 

1) DIvide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.

2) Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.

3) Combine : Conquer한 문제들을 통합하여 원래의 문제의 답을 얻는다.

 

[백준] 2630번 : 색종이 만들기 - JAVA [자바] (tistory.com)

 

[백준] 2630번 : 색종이 만들기 - JAVA [자바]

www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차

st-lab.tistory.com

 

1) 각각의 행과 열의 시작점(초기는 (0,0)이 기준)에서 현재 파티션에 대하여 모두 같은 색상인지 체크를 먼저 해야 함

2) 색상이 같다면 해당 색상의 개수를 1 증가 시키고 함수를 종료 한다.

3) 색상이 같지 않다면, 4등분 하여 각 부분 문제로 쪼개어 문제를 푼다.

 

정답 

 

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

public class Main {
    static int cnt_w = 0;
    static int cnt_b = 0;
    static int board[][];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        board = new int[n][n];
       
        for(int i=0; i<n; i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        partition(0,0,n);
        bw.write(cnt_w+"");
        bw.newLine();
        bw.write(cnt_b+"");
        
        bw.flush();
        bw.close();
    }
    
    //색종이의 색이 다를 경우 변의 길이를 자름
    static void partition(int row, int col, int size)
    {
        //색이 같을 경우는 각 카운트 증가
        if(check(row,col,size))
        {
            if(board[row][col]==0)
            {
                cnt_w++;
            }
            else
            {
                cnt_b++;
            }
            return;
        }
        
        //색이 다를 경우 
        int newSize = size/2; //절반
        
        //재귀 호출
        partition(row,col,newSize); //2사분면
        partition(row,col+newSize,newSize); //1사분면
        partition(row+newSize,col,newSize); //3사분면
        partition(row+newSize,col+newSize, newSize); //4사분면
    }
    
    //색종이의 색이 같은지 다른지 확인
    static boolean check(int row, int col, int size)
    {
        int color = board[row][col]; //첫 번째 원소를 기준으로 검사 
        
        for(int i=row; i<row+size; i++)
        {
           for(int j=col; j<col+size; j++)
           {
               //색상이 같지 않다면 false를 리턴
               if(board[i][j] != color)
               {
                   return false;
               }
           }
        }
        //검사가 모두 통과했다는 의미이므로 true 리턴
        return true;
    }
}

 

 

'Java > 백준' 카테고리의 다른 글

[JAVA] 백준 1790 종이의 개수  (0) 2024.03.06
[JAVA] 백준 1992 쿼드 트리  (1) 2024.03.06
[JAVA] 백준 13305 주유소  (1) 2024.03.04
[JAVA] 백준 1541 잃어버린 괄호  (0) 2024.03.04
[JAVA] 백준 11399 ATM  (0) 2024.03.04