(JAVA)백준 문제 풀이 - 분할 정복 단계 - 1780번 종이의 개수 (실버2)

이번 문제는 2차원 행렬에 담긴 데이터를 판단하여 0,1,-1로 분류하여 같지 않으면 9등분 하고 맞으면 갯수를 구하는 문제이다. 문제 자체가 크게 어렵지 않아 금방 풀어낼 수 있었다. 그럼 어떻게 풀었는지 살펴보자.

---

분할 정복이란?

분할 정복이란 큰 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 각 부분 문제의 답으로부터 전체의 답을 계산하는 알고리즘이다.

언뜻 봐서는 재귀호출과 비슷해 보이지만, 일반 재귀 호출과 분할 정복의 가장 큰 차이는 일반 재귀 호출은 문제를 한 조각과 나머지 전체로 나눈다면 분할 정복은 문제를 거의 같은 크기의 부분 문제로 나눈다는 점이다.

 

분할 정복은 3가지 과정으로 이루어 지는데

1. 문제를 더 작은 문제로 분할하는 과정

2. 각 문제에 대한 답을 원래 문제에 대한 답으로 병합하는 과정

3. 더이상 답을 분할하지 않고 곧장 풀 수 있는 작은 문제

이 3가지 케이스로 구성된다.

 

그럼 문제를 살펴보자.

우리에게 주어진 것은 무조건 3의 제곱수로 들어오게 된다. (즉, 3의 배수이다)

따라서 우리는 전체 값을 2차원 배열에 담고, 배열을 순회하면서 값을 비교한 후 값이 모두 같다면 해당 값의 갯수를 증가 시키고 아니라면 전체를 9등분하여 같은 과정을 반복하면 된다.

나는 이전에 풀었던 문제에서 힌트를 얻어서 x축의 시작값과 y축의 시작값, 전체 사이즈를 받고 2차원 반복문을 순회하며 카운트 하는 방법으로 하였다.

 

public static void check(int x, int y, int size) {
        boolean isEqual = true;

        if (isEqual) {
            result[temp + 1]++;
        } else {
            int newSize = size / 3;
            for (int i = y; i < y + size; i += newSize) {
                for (int j = x; j < x + size; j += newSize) {
                    check(j,i,newSize);
                }
            }
        }

 

중요 코드를 보면 해당 케이스가 전체가 동일한지 아닌지 isEqual 변수를 통해 기록하고, 해당 변수를 통하여 값이 모두 같으면 갯수를 증가 시키고 아니라면 2차 반복문에서 x축과 y축을 전체 크기를 3으로 나눈 값 만큼 증가시켜서 연속적으로 던지게 하였다.

이렇게 하면 전체 9가지의 갯수를 모두 테스트 할 수 있게 되는 것이다.

결과는 크기 3의 배열을 만들고 각 값의 +1을 해주어 바로 더하게 했는데 이렇게 하면 -1,0,1의 값이 0,1,2가 되므로 단일 배열로 받아서 바로 계산을 할 수 있었다.

그렇다면 실제 코드를 살펴보자.

---

코드를 살펴보자

import java.io.*;
import java.util.*;

class Main{
    public static int n;
    public static int[][] arr;
    public static String[] str;
    public static int[] result;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        result = new int[3];

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

        check(0, 0, n);
        for (int num : result) {
            System.out.println(num);
        }

    }

    public static void check(int x, int y, int size) {
        boolean isEqual = true;
        int temp = arr[y][x];

        for (int i = y; i < y + size; i++) {
            if (!isEqual) break;
            for (int j = x; j < x + size; j++) {
                if(temp != arr[i][j]) {
                    isEqual = false;
                    break;
                }
            }
        }

        if (isEqual) {
            result[temp + 1]++;
        } else {
            int newSize = size / 3;
            for (int i = y; i < y + size; i += newSize) {
                for (int j = x; j < x + size; j += newSize) {
                    check(j,i,newSize);
                }
            }
        }

    }
}

 

코드를 살펴보면 크게 어렵지 않다.

우선 입력받은 크기만큼의 2차원 배열을 만들고 각 입력값을 위치에 담는다.

그후 초기값 0,0,입력 받은 크기로 재귀 함수를 돌리게 되는데, 재귀함수는 각 값을 비교하여 동일하면 isEqual 변수를 True로 아니라면 False로 설정해 두었다.

 

그 후, 마지막에 If문으로 같으면 정답 배열에 해당 인덱스에 갯수를 더해주고 다니면 3으로 나누어 재귀하는 것으로 한번에 구현하였다.

 

분할 정복이 큰 문제를 나누어 생각하는 만큼 크게 어렵지도 않고 문제를 설계하는 과정 자체가 재미있었던것 같다.

---

참고자료

https://velog.io/@turtle601/%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5