백준 1780번 종이의 개수 (자바) 풀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

34215

20278

15221

58.515%

문제

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

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 복사

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

예제 출력 1 복사

10
12
11

 

풀이

해당 문제는 바로 직전에 업로드한 2630번과 거의 같다.

전 문제에 엄청 헤맸었기 때문에 응용을 할 수 있는 문제를 찾아야겠다 하고 찾으니 바로 등장했다.

해당 문제도 단순히 문제에서 제시하는 힌트를 그대로 이해하면 된다.

• 모든 부분의 수가 같다면 나누지 않는다.
• 같지 않다면 9 등분한다. (종이는 보통 9의 배수가 면적으로 주어진다.)

 

이 두 조건을 두고 봤을 때, 전 문제와 다른 것은 단순히 몇 등분을 하냐 와 조건이 몇 개인가? 를 따지면 된다.

 

이 문제도 마찬가지로 좌표를 이용해서 풀이해야하기 때문에 어렵게 느껴질 수 있다.

 

하지만 한번 문제의 유형을 익힌다면 전혀 어렵지 않으니 이해가 어렵다면 자존심을 굽히고 풀이를 참고하자.

 

 

 

마찬가지로 계속 나눌거라는 힌트가 주어졌기 때문에 재귀용법이 사용될 것이다.

브레이크포인트를 먼저 잡아주자. 바로 각각 부분의 숫자가 모두 같아야 한다는 점이다.

말 그대로 기준점을 잡아 2중 반복문으로 순회하면서 데이터가 같다면 true, 아니라면 false를 반환하는 체크용 메서드를 선언하자

 

    public static boolean check(int row,int col,int size){
        int pivot = paper[row][col];
        for(int i=row; i<row+size;i++){
            for(int j=col;j<col+size;j++){
                if(paper[i][j]!=pivot){
                    return false;
                }
            }
        }
        return true;
    }

마찬가지로 배열과 카운트에 대한 변수는 모두 정적변수로 선언했다.

 

그리고 브레이크 포인트를 만들었으니 재귀함수를 만들면 된다.

 

마찬가지로 9 등분이라는 건 각 변을 3으로 나눠서 체크하는 것이기 때문에 사이즈를 3 등분해서 함수를 호출해주면 된다.

 

그런데 여기서는 9등분이라고 했으면, 메서드를 9번 호출해야 되는데 , 단순히 그냥 한 줄씩 작성해 9번 호출할까..?

 

에 대한 대답은 그러면 16등분 25등분 이러면 어떻게 하시려고..?

 

이중 반복문으로 각각 로우와 칼럼에 늘어나는 인덱스*등분 사이즈 (나눠진 사이즈)를 더해가면서 함수를 호출하도록 하면 된다.

 

마찬가지로 브레이크 포인트를 먼저 선언해주고 통과했을 때 해당 값들이 어떠한 숫자로 이루어져 있는지 (-1,0,1 중에 하나)를 체크해서 카운트를 ++해주도록 하면 된다.

 

 public static void divide(int row,int col,int size){
        if (check(row, col, size)) {
            if(paper[row][col]==-1){
                minus++;
            }else if(paper[row][col]==0){
                zero++;
            }else{
                plus++;
            }
            return;
        }
        int[] move = {0,1,2};
        int newSize= size/3;
        for(int i=0; i<3;i++){
            for(int j=0; j<3;j++){
                divide(row+(i*newSize),col+(j*newSize),newSize);
            }
        }
    }

이렇게 하면 깔끔하게 표현이 가능하다.

 

package baekjoon.a1780;

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

public class a1780 {
    public static int minus =0;
    public static int zero =0;
    public static int plus =0;
    public static int[][] paper;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        paper = new int[N][N];
        for(int i=0; i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N;j++){
                paper[i][j]= Integer.parseInt(st.nextToken());
            }
        }
        divide(0,0,N);
        System.out.println(minus);
        System.out.println(zero);
        System.out.println(plus);
    }

    public static void divide(int row,int col,int size){
        if (check(row, col, size)) {
            if(paper[row][col]==-1){
                minus++;
            }else if(paper[row][col]==0){
                zero++;
            }else{
                plus++;
            }
            return;
        }
        int[] move = {0,1,2};
        int newSize= size/3;
        for(int i=0; i<3;i++){
            for(int j=0; j<3;j++){
                divide(row+(i*newSize),col+(j*newSize),newSize);
            }
        }
    }
    public static boolean check(int row,int col,int size){
        int pivot = paper[row][col];
        for(int i=row; i<row+size;i++){
            for(int j=col;j<col+size;j++){
                if(paper[i][j]!=pivot){
                    return false;
                }
            }
        }
        return true;
    }
}