백준 1780 종이의 개수 - 자바(Java)

문제 링크

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

 

---

1. 문제

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

 

2. 문제 관찰 과정 및 풀이

 

2-1. 문제 관찰 과정

우선 종이를 2차원배열에 저장해야겠다는 생각이 들었다.

또한 예제를 보면 1칸 단위까지 들어가므로 size가 1이 되면 해당 값을 카운트에 올려주어야한다.

 

값이 바뀌는지 비교하기 위해 처음 값을 저장해 두어야겠다고 생각했다.

 

만약 다른게 있다면 재귀를 실행하고 다른게 없다면 저장한 값의 카운트를 올린다.

2-2. 문제 풀이

왼쪽위의 좌표를 매개변수로 재귀 함수를 실행하였다.

 

첫 좌표의 값을 저장하고 for문을 돌면서 값이 다른게 있나 검사한다.

값이 다른게 없다면 저장했던 값의 카운트를 증가하고 return

값이 다른게 있다면 size를 나누기 3한뒤 나누기 3한 값으로 9개의 좌표로 재귀 함수를 실행한다.

 

size가 1이 된다면 해당 값의 카운트를 증가 시키고 return;

 

3. 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int[][] map;
    public static int[] count = {0 , 0 , 0};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        for(int i = 0; i< n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j<n;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        recur(n, 0, 0);

        for (int i : count) {
            sb.append(i).append("\n");
        }
        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }

    public static void recur(int size, int x , int y){
        if(size == 1){
            count[map[x][y] + 1]++;
            return;
        }
        int tmp = map[x][y];
        boolean flag = true;
        for(int i = x; i < x + size ; i++){
            for(int j = y ; j < y + size ; j++){
                if(tmp != map[i][j]){
                    flag = false; //다른게 있다.
                }
            }
        }

        if(flag){

            count[map[x][y] + 1]++;
            return;
        }
        //다른게 있다면 recur해야한다.
        int newSize = size/3;
        recur(newSize, x, y);
        recur(newSize, x + newSize, y);
        recur(newSize, x + newSize *2, y);

        recur(newSize, x, y + newSize);
        recur(newSize, x + newSize, y + newSize);
        recur(newSize, x + newSize *2, y+ newSize);

        recur(newSize, x, y + newSize * 2);
        recur(newSize, x + newSize, y + newSize * 2);
        recur(newSize, x + newSize *2, y + newSize * 2);

    }
}

3-1. 실행 결과

4. 여담