[백준] 1780번 - 종이의 개수 (자바 /Java)

 

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

 

1780번: 종이의 개수

 

 

종이의 개수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	24882	14709	11083	58.918%

 

 

문제

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

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.

(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

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

 

입력

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

 

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 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	10 12 11

 

---

 

문제 접근 방법

분할정복 (Divide and conquer) 문제로 접근했다.
따로 solve라는 함수를 정의하여 배열의 시작하는 X와 Y를 받고, 탐색해야하는 길이를 입력했다.
예제를 예로 들면, 처음에는 전체 9x9의 모든 배열을 보고,
그다음에는 각각 (0,0) (0,3) (0,6) / (3,0) (3,3) (3,6) / (6,0) (6,3) (6,6) 이렇게 6개의 점들에서
각각 길이 9/3 만큼의 작은 배열을 보는 재귀 함수를 짠것.

---

소스코드

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

public class Main {
    static int[][] paper;
    static int N;
    static int countMinus;
    static int countZero;
    static int countPlus;

    static void solve(int startX,int startY, int length){
        int num = paper[startX][startY];
        boolean checker = true;
        OuterLoop:
        for(int i = startX; i<(startX+length);i++){
            for(int j = startY; j<(startY+length);j++) {
                if(paper[i][j] != num){
                    checker = false;
                    break OuterLoop;
                }
            }
        }
        if(checker){
            if(num == -1) {countMinus++;}
            else if(num == 0) {countZero++;}
            else {countPlus++;}

        }else{
            for(int i=startX; i<startX+length;i=i+length/3){
                for(int j=startY; j<startY+length;j=j+length/3){
                    solve(i,j,length/3);
                }
            }
        }

    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
            }
        }
        countMinus = countZero = countPlus =0;
        solve(0,0,N);
        System.out.print(countMinus+"\n"+countZero+"\n"+countPlus);

    }
}