[백준] 1780 - 종이의 개수 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

1780번: 종이의 개수

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력
첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

접근방법

 3의 제곱수로 이루어진 N * N 배열이 있을 때, 3의 제곱수로 이루어진 정사각형의 개수를 구하는 문제이다. 단, 정사각형 내부에 있는 모든 수는 동일해야 하며, -1,0,1로 구분하여 종이의 개수를 요구하고 있다. 예를 들어, 9 * 9의 배열이 있을 때, (0,0) ~(2,2) 범위 내에 모든 수가 1이라면, 1로 이루어진 종이의 개수를 추가하면 된다. N의 크기가 클수록, 재귀적으로 일정한 순서를 구성하여 문제를 해결해야 한다. 이런 재귀적인 특성을 인지하고 풀이로 들어가자. 

풀이

 사람들 마다 재귀 함수를 만드는 방법이 어느 정도 있겠지만, 나는 주로 이렇게 푼다.

 

void recursive(Params...){
	//종결조건

	//처리 및 반복조건


}

 우선적으로 종결 조건을 통해 재귀를 탈출할 수 있는 방안을 마련해두고, 처리 및 재귀 함수를 부르는 과정을 진행한다.

이렇게 하면, 처리 및 재귀 함수 부분에서 흐름만 제어를 잘해도 무한루프에 빠지는 것을 많이 막아줄 수 있다.

 

 다시 문제로 돌아가서,문제의 기준에 의해 다음과 같은 순서로 판별할 수 있다.

 

1. 현재 사이즈에 있는 배열의 모든 원소가  같은 숫자 인가?
2. 아니라면, 현재 사이즈보다 3배 작은 사이즈로 확인하자. 

 재귀 함수를 구현할 때는 가장 작은 단위를 먼저 생각해보는 것이 좋다. 여기서는 3이 최소 숫자이므로, 3으로 생각해보겠다. 3 x 3 배열이 -1,0,1을 조금씩 섞어 가지고 있다고 생각해보자. 위에 순서를 적용해보자. 재귀 함수를 한번 호출할 때마다 'Depths]로 표현하겠다.

 

1. 1] 사이즈 3으로 현재 있는 배열에 모든 원소가 같은 숫자인가? N ->2번 조건 이동
2. 1] 현재 사이즈의 1/3인 사이즈 1로 확인하자. -> 사이즈가 1로 줄었으므로, 9개로 나누어 사이즈 1인 재귀 
3. 2] 사이즈 1로 현재 있는 배열에 모든 원소가 같은 숫자 인가? Y -> 해당 숫자를 증가시키고 상위 이동
4. 1] 사이즈 1인 배열 하나를 확인했으므로 다음 배열을 확인하자 -> 사이즈 1인 재귀
5. 2] 사이즈 1로 현재 있는 배열에 모든 원소가 같은 숫자 인가? Y -> 해당 숫자를 증가시키고 상위 이동
6. 2 -3번 과정을 도합 9번 반복
7. 함수 종료

재귀 함수의 특징은 호출 시 들어가는 인자의 변화를 줄 뿐 하는 일은 같아야 한다. 여기서 공통적으로 나타나는 것을 정리하면 다음과 같다.

 

• 현재 사이즈에 있는 모든 원소가 같은지 확인
• 다르다면 9개로 쪼개서 재귀 호출

이것이 이 문제의 끝이다.

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main test =new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int size = Integer.parseInt(br.readLine());

        int[][] arr  = new int[size][size];

        for (int i = 0 ; i < arr.length ; i++){
            StringTokenizer stk = new StringTokenizer(br.readLine()," ");
            for (int j = 0 ; j < arr[i].length; j++){
                arr[i][j] = Integer.parseInt(stk.nextToken());
            }
        }


        int[] output = solution(arr,0,0,new int[3],size);
        for (int answer :output){
            System.out.println(answer);
        }
    }

    int[] solution (int[][] arr,int start_y,int start_x,int[] result,int size){

        //해당 기준좌표부터 size 영역만큼을 검사
        if(isFull(arr,start_y,start_x,size)){

            //모두 같은 수라면 데이터 증가
            if(arr[start_y][start_x]==-1){
                result[0]+=1;
            }else if( arr[start_y][start_x]==0){
                result[1]+=1;
            }else{
                result[2]+=1;
            }
        }else {

            //size 만큼 뛰어넘는다
            for (int i = start_y; i < start_y + size; i += size/3) {
                for (int j = start_x; j < start_x + size; j += size/3) {
                    //System.out.println("현재 좌표 : " + i + " " + j + "\t size : " + size);
                    {

                        //i,j 기준으로부터 size만큼의 모든 영역
                        int[] tmp = solution(arr, i, j, result, size / 3);

                        int k = 0;
                        for (int data : tmp) {
                            result[k++] = data;
                        }

                    }
                }
            }
        }

        return result;
    }

    //현재 좌표를 기준으로 size x size 배열의 모든 요소가 같은지 검사
    boolean isFull(int[][] arr, int start_y,int start_x, int target_size){

        int compare_val = arr[start_y][start_x];
        for (int i = start_y ; i < start_y+target_size ; i++){
            for (int j = start_x ; j < start_x + target_size; j++){
                if(compare_val != arr[i][j]){
                    return false;
                }
            }
        }

        return true;
    }




}

 

결과

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.