[백준/Java] 1780번 : 종이의 개수

[문제]

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

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

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

[조건]

• 시간 제한 : 2초
• 메모리 제한 : 256MB

[입력]

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

[출력]

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

[문제 풀이]

• 배열의 첫 요소를 prev에 저장
• 배열의 크기만큼 돌며 요소 값을 prev와 비교하다가 다르다면 9개의 종이로 나뉘어야함
• 현재 배열의 시작점이 r, c이므로 이를 고려해 9개로 나뉜 배열 시작점 조정
• 배열의 크기만큼 돌며 요소 값을 prev와 비교하다가 같다면 9개의 res배열에서 해당 인덱스++

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

public class boj_1780_종이의개수 {
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, prev;
    static int[] res = new int[3];
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        for(int r=0; r<N; r++) {
            st = new StringTokenizer(br.readLine());
            for(int c=0; c<N; c++) {
                arr[r][c] = Integer.parseInt(st.nextToken());
            }
        }
        
        check(N, 0, 0);
        for(int i=0; i<3; i++) {
        	sb.append(res[i]).append("\n");
        }
        System.out.println(sb);
        
    }
    
    static int check(int n, int r, int c) {
        prev = arr[r][c];
        for(int row=r; row<r+n; row++) {
            for(int col=c; col<c+n; col++) {
                if(arr[row][col]!=prev) {
                	int nine = n/3;
                    check(nine, r, c);
                    check(nine, r, c+nine);
                    check(nine, r, c+nine*2);
                    check(nine, r+nine, c);
                    check(nine, r+nine, c+nine);
                    check(nine, r+nine, c+nine*2);
                    check(nine, r+nine*2, c);
                    check(nine, r+nine*2, c+nine);
                    check(nine, r+nine*2, c+nine*2);
                    return 0;
                }
            }
        }
        return res[prev+1]++;
        
    }
}

 

[소감]

• 이전까지 재귀 함수를 짤 때는 기저 조건을 처음에 처리해줬음
• 위와 같은 구성이 필수가 아니라 상황에 따라 다양하게 return 처리를 할 수 있다는 것 깨달음

 

출처 : 백준 https://www.acmicpc.net/problem/1780