[알고리즘-자바] 백준 1780번 종이의 개수

아래 설명이 이해가 되지 않을 수도 있다. 중간에 이해가 어렵다면 가장 아래의 추가 사항을 확인하자.

문제

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

1780번: 종이의 개수

언어 

자바 Java

로직

하나의 숫자로만 이루어진 종이인지 확인

(0, 0) 지점부터 탐색을 하면서 (0, 0)에 저장된 숫자와 다른 숫자를 갖는 칸이 있는지 확인한다. 없다면 반복문을 벗어나 밖의 코드를 수행하고, 있다면 아래의 종이 9등분 과정을 거친다.

static void count(int curX, int curY, int[][] arr, int size) {
    for (int i = curX; i < curX + size; i++) {
        for (int j = curY; j < curY + size; j++) {
            if (arr[j][i] != arr[curY][curX]) {
            // .. 생략
            }
        }
    }
    // .. 생략
}

종이 9등분

n의 경우 3^k이 입력된다. 따라서 9등분을 하기 위해서는 기존 크기에서 3으로 나누어야 9등분이 된다. 

ex) n=27이면 낱개 27개로 이루어진 1개의 종이가 만들어진다. 이때 27 / 3은 9이므로 9x9 크기를 갖는 9개의 종이가 만들어진다.

static void count(int curX, int curY, int[][] arr, int size) {
    for (int i = curX; i < curX + size; i++) {
        for (int j = curY; j < curY + size; j++) {
            if (arr[j][i] != arr[curY][curX]) {
                size /= 3; // 3으로 나누어야 9등분이 된다.
                // .. 생략
            }
        }
    }
    // .. 생략
}

재귀

종이 9등분을 거치고 9개의 공간에 대해서 맨 처음에 했던 하나로만 이루어진 종이인지 확인한다. k와 w에 대한 for문이 이해되지 않을 수도 있으므로 코드를 하나 더 남기겠다.

static void count(int curX, int curY, int[][] arr, int size) {
    for (int i = curX; i < curX + size; i++) {
        for (int j = curY; j < curY + size; j++) {
            if (arr[j][i] != arr[curY][curX]) {
                size /= 3;
                for(int k = 0; k < 3; k++) {
                    for(int w= 0; w < 3; w++) {
                        count(curX + size * w, curY + size * k, arr, size);
                    }
                }
                return;
            }
        }
    }
    // .. 생략
}

count(curX, curY, arr, size);
count(curX + size, curY, arr, size);
count(curX + size * 2, curY, arr, size);
count(curX, curY + size, arr, size);
count(curX + size, curY + size, arr, size);
count(curX + size * 2, curY + size, arr, size);
count(curX, curY + size * 2, arr, size);
count(curX + size, curY + size * 2, arr, size);
count(curX + size * 2, curY + size * 2, arr, size);

n = 일때, 9등분

숫자 개수 확인

number는 크기 3으로 이루어진 배열이다. 인덱스 순서대로 -1, 0, 1의 숫자 개수를 저장한다.

static void count(int curX, int curY, int[][] arr, int size) {
    for (int i = curX; i < curX + size; i++) {
        for (int j = curY; j < curY + size; j++) {
            if (arr[j][i] != arr[curY][curX]) {
            // .. 생략
            }
        }
    }
    number[arr[curY][curX] + 1]++;
}

---

코드

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

public class Main {
    static int[] number = new int[3]; // -1, 0, 1

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(input[j]);
            }
        }

        count(0, 0, arr, n);

        for (int num : number) {
            System.out.println(num);
        }
    }

    static void count(int curX, int curY, int[][] arr, int size) {
        for (int i = curX; i < curX + size; i++) {
            for (int j = curY; j < curY + size; j++) {
                if (arr[j][i] != arr[curY][curX]) {
                    size /= 3;
                    for(int k = 0; k < 3; k++) {
                        for(int w= 0; w < 3; w++) {
                            count(curX + size * w, curY + size * k, arr, size);
                        }
                    }
                    return;
                }
            }
        }
        number[arr[curY][curX] + 1]++;
    }
}

---

추가 사항

위의 설명이 이해가 어렵다면 아래 해설을 먼저 확인해 보자.

https://server-technology.tistory.com/74

[알고리즘-자바] 백준 2630번 색종이 만들기