(Java) 백준 종이의 갯수 [분할정복, 재귀]

 

- 목차

 

소개.

아래 링크는 "백준 종이의 갯수" 문제의 웹링크입니다.

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

1780번: 종이의 개수

 

 

문제 소개.

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

 

 

문제 분석.

종이의 갯수 문제는 분할 정복과 관련된 알고리즘 문제입니다.

분할 정복과 관련된 여러 힌트들이 있습니다.

 

첫번째로 "-1", "0", "1" 로 채워진 정사각행렬을 분할하는 패턴이 주어집니다.

그리고 분할된 정사각행렬이 동일한 값을 가질 때까지 분할을 반복합니다.

이러한 반복의 패턴이 주어지는 문제는 분할정복 방식으로 접근해야합니다.

 

두번째로 제곱 수로 이루어진 정사각행렬이라는 점입니다.

분할정복을 구현하기 위해서 반드시 제곱수의 정사각행렬이 문제로 주어질 필요는 없습니다.

하지만 레벨이 낮은 분할정복 문제에서는 제곱수의 정사각행렬이 문제로 주어지곤 합니다.

 

아래 이미지와 같이 분할된 정사각행렬이 동일한 값을 가질때까지 분할과 검증을 반복해야합니다.

 

 

문제 풀이.

 

import java.util.Scanner;

public class Main {


  static int aCount = 0;
  static int bCount = 0;
  static int cCount = 0;
  public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[][] map = new int[n][n];
    scanner.nextLine();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        map[i][j] = scanner.nextInt();
      }
    }

    divide(map, 0, 0, n - 1, n - 1);
    System.out.println(aCount);
    System.out.println(bCount);
    System.out.println(cCount);

  }

  static void divide(int[][] map, int startY, int startX, int endY, int endX) {

    if (conquer(map, startY, startX, endY, endX, -1)) {
      aCount++;
      return;
    }
    if (conquer(map, startY, startX, endY, endX, 0)) {
      bCount++;
      return;
    }
    if (conquer(map, startY, startX, endY, endX, 1)) {
      cCount++;
      return;
    }



    int midY = (endY - startY) / 3 + startY;
    int midX = (endX - startX) / 3 + startX;
    int mid2Y = (int) Math.floor(((double) endY - startY) / 3 * 2) + startY;
    int mid2X = (int) Math.floor(((double) endX - startX) / 3 * 2) + startX;

    // 1
    divide(map, startY, startX, midY, midX);
    // 2
    divide(map, startY, midX + 1, midY, mid2X);
    // 3
    divide(map, startY, mid2X + 1, midY, endX);

    // 4
    divide(map, midY + 1, startX, mid2Y, midX);
    // 5
    divide(map, midY + 1, midX + 1, mid2Y, mid2X);
    // 6
    divide(map, midY + 1, mid2X + 1, mid2Y, endX);

    // 7
    divide(map, mid2Y + 1, startX, endY, midX);
    // 8
    divide(map, mid2Y + 1, midX + 1, endY, mid2X);
    // 9
    divide(map, mid2Y + 1, mid2X + 1, endY, endX);
  }

  static boolean conquer(int[][] map, int startY, int startX, int endY, int endX, int value) {
    for (int i = startY; i <= endY; i++) {
      for (int j = startX; j <= endX; j++) {
        if (map[i][j] != value) return false;
      }
    }
    return true;
  }

}

/*
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

*/