[Java+Python]1780번, 종이의 개수

목차

• 문제
• 입력
• 출력
• 풀이
  • Java
  • Python
  • Performance

 

분할 정복 단계

 

[Java+Python]2630번, 색종이 만들기

[Java+Python]1992번, 쿼드 트리

[Java+Python]1629번, 곱셈

[Java+Python]11401번, 이항 계수 3

[Java+Python]2740번, 행렬 곱셈

[Java+Python]10830번, 행렬 제곱

[Java+Python]11444번, 피보나치 수 6

[Java+Python]6549번, 히스토그램에서 가장 큰 직사각형

 

문제

 

N×N크기의 행렬로 표현되는 종이가 있다. 

종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 

우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

 

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. 1. 이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 1. 의 과정을 반복한다

이와 같이 종이를 잘랐을 때,

 

1. -1로만 채워진 종이의 개수,
2. 0으로만 채워진 종이의 개수,
3. 1로만 채워진 종이의 개수

를 구해내는 프로그램을 작성하시오.

 

입력

 

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

 

출력

 

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

 

풀이

 

이전 두 문제에서 연습한 분할정복 알고리즘을 아홉 조각으로 늘린 문제이다.

 

비슷한 문제가 세 개째니까 바로 문제 해결을 위한 알고리즘을 정리하자.

 

1. 입력으로 주어진 영상의 한 변의 길이 n을 저장하고 이를 이용해 n x n 이차원 배열(리스트) paper를 초기화한다.
2. -1, 0, 1의 개수를 저장할 크기가 3인 count를 생성 및 초기화해 준다.
3. 재귀함수 quadrant를 호출한다. 해당 함수의 작동 방식은 아래와 같다.
   
   
   1. isSame 메서드를 호출해 현재 분할 영역이 전부 같은 값인지 확인한다.
   2. 전부 같은 값이라면 count[paper[row][col] + 1]의 값을 +1 해준다.
      
      
      1. 여기서 count의 인덱스가 <paper[row][col] + 1>인 이유는 -1, 0, 1을 각각 0, 1, 2 인덱스에 저장하기 위함이다.
   3. 전부 같은 값이 아니라면 한 변의 길이를 3으로 나눈 뒤 9등분해서 재귀호출을 진행한다.
   4. 모든 영역이 같은 값을 가질 때까지 반복한다.
4. -1, 0, 1의 개수를 차례대로 출력한다.

 

Java

 

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

public class Prob1780 {

	static int[][] paper;
	static int[] count = new int[3];

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int 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());
			}
		}

		divide(0, 0, n);

		for (int i = 0; i < 3; i++) {
			System.out.println(count[i]);
		}
	}

	private static void divide(int row, int col, int size) {

		if (isSame(row, col, size)) {
			count[paper[row][col] + 1]++;
			return;
		}

		int newSize = size / 3;

		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				divide(row + newSize * i, col + newSize * j, newSize);
			}
		}
	}

	private static boolean isSame(int row, int col, int size) {

		int color = paper[row][col];

		for (int i = row; i < row + size; i++) {
			for (int j = col; j < col + size; j++) {
				if (paper[i][j] != color) {
					return false;
				}
			}
		}

		return true;
	}
}

 

Python

 

import sys

n = int(sys.stdin.readline().rstrip())
paper = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(n)]
count = [0] * 3


def is_same(row, col, size):
    color = paper[row][col]
    for i in range(row, row + size):
        for j in range(col, col + size):
            if paper[i][j] != color:
                return False
    return True


def divide(row, col, size):
    if is_same(row, col, size):
        count[paper[row][col] + 1] += 1
        return

    new_size = size // 3

    for i in range(3):
        for j in range(3):
            divide(row + new_size * i, col + new_size * j, new_size)


divide(0, 0, n)

print(*count, sep='\n')

 

Performance