백준 1780 종이의 개수 알고리즘 자바 JAVA

 

 

백준 1780 종이의 개수 알고리즘 문제

 

백준 1780 종이의 개수 문제는 분할정복 알고리즘 방법으로 풀수 있는 문제다. 주어진 숫자들을 비교해서 -1,0,1 세 가지 경우의 수를 판별해서 종이의 개수를 카운팅 하는 문제다.

 

기본적인 논리는 백준 1992번 쿼드트리 문제와 동일하다. 다만 다른점은 색종이의 갯수가 N/3 단위로 쪼개진다는 것이다. 입력값 맨 처음 주어지는 숫자 N은 3의 지수승으로 만들어진 숫자다. N(1 ≤ N ≤ 37, N은 3k) 동일한 알고리즘으로 구현하되, 색종이를 쪼개는 분기를 9번씩 돌아가면서 진행해야 한다는 점이 유일한 차이점이다.

 

 

 

백준 1992번 쿼드트리 분할정복 알고리즘 JAVA 자바

 

 

 

분할정복 알고리즘

 

분할정복 알고리즘은 큰 문제를 작은 문제로 쪼개가면서 출력값을 구하고, 서브루틴에서 얻은 결과값을 모아서 전체 문제의 결과를 어어가는 과정이다. 문제를 쪼개는 과정에서 필수적으로 들어가야 하는 로직들을 구현한다. 백준 1780번 색종이 개수 문제에서는 3가지 로직이 필요하다.

 

1. 숫자가 같은지 다른지 구분하는 로직

2. 모두 같은 숫자라면 어떤 숫자인지 확인하는 로직

3. 색종이를 X개로 나누는 로직

 

출력값은 -1로 구성된 종이, 0으로 구성된 종이, 1로 구성된 종이 순으로 출력하면 된다. StringBuilder 클래스를 사용하지 않고, System.out.println()으로 풀었는데도, 시간초과 오류는 발생하지 않았다. 

 

 

백준 1780 색종이 개수 문제

 

 

색종이가 나눠지는 과정

처음 주어진 숫자들을 비교하는 로직을 거쳐 색종이를 나눠야 할지 말아야 할지를 결정한다. 숫자의 값이 다를 경우 색종이는 한 변이 N/3인 색종이로 쪼개지게 된다. 이 때 색종이는 9개의 조각으로 쪼개진다. NxN으로 구성된 정사각형의 숫자가 동일한 값이 나올 때 까지 이 과정은 계속 반복된다. 

 

동일한 숫자를 얻은 경우가 나오면 반복 로직은 멈추게 되고, static으로 선언된 전역변수에 카운팅을 하면서 상위 로직으로 단계별로 복귀하게 된다. 최종적으로 모든 로직이 최상단 로직으로 복귀하게 되면 색종이의 값을 출력하고 프로그램은 종료된다.

 

 JAVA CODE

/*
    Owner : Developer Blog
    Title : 종이의개수(9개)
    Algorithm : 분할정복 알고리즘
    Date : 2022-03-02
*/

import java.util.Scanner;

public class A_1780 {
    public static int[][] arr;
    public static int firstPaper;
    public static int secondPaper;
    public static int thirdPaper;

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();

        arr = new int[N][N];

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                arr[i][j] = in.nextInt();
            }
        }

        paperFinder(0,0,N);
        System.out.println(firstPaper);
        System.out.println(secondPaper);
        System.out.println(thirdPaper);

    }
    public static Boolean checkNumber(int row, int col, int N){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(arr[row][col] != arr[i+row][j+col]) return false;
            }
        }
        return true;

    }
    public static void checkColor(int row, int col){
        switch(arr[row][col]){
            case -1:
            firstPaper++;
            break;

            case 0:
            secondPaper++;
            break;

            case 1:
            thirdPaper++;
            break;

        }

    }
    public static void paperFinder(int row, int col, int N){
        if(checkNumber(row,col,N)){
            checkColor(row, col);
        }else{
            paperFinder(row,        col,        N/3);
            paperFinder(row+N/3,    col,        N/3);
            paperFinder(row+N*2/3,  col,        N/3);
            paperFinder(row,        col+N/3,    N/3);
            paperFinder(row+N/3,    col+N/3,    N/3);
            paperFinder(row+N*2/3,  col+N/3,    N/3);
            paperFinder(row,        col+N*2/3,  N/3);
            paperFinder(row+N/3,    col+N*2/3,  N/3);
            paperFinder(row+N*2/3,  col+N*2/3,  N/3);
        }

    }
}

문제를 푼 결과 총 소요시간은 3200ms가 넘어갔는데도 맞았습니다 결과가 나왔다.