[Java] 백준 #1780 종이의 개수

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

1780번: 종이의 개수

• N x N 행렬 종이 → 각각 -1, 0, 1 중 하나 저장
• 규칙에 따라 적절한 크기로 종이 자르기
  1. 종이가 모두 같은 수 → 그대로 사용
  2. 모두 같은 수 x → 같은 크기의 종이 9개로 자르고 각각의 잘린 종이에 대하여 1번 과정 반복

이와같이 종이를 잘랐을 때 -1, 0, 1로만 채워진 종이의 개수 각각 구하기

• N은 3^k꼴, 1 ≤ N ≤ 3^7

💡 알고리즘

분할 정복, 재귀

💡 접근

다음 두 함수로 나누어서 구현

• 배열내 원소값이 모두 동일한지 확인하는 함수 isDiff()
• isDiff() 호출 → true → 해당값의 count 증가, isDiff() 호출 → false → 배열 9개로 쪼개서 재귀호출하는 함수 splitAndCheck()

이 문제를 쉽게 해결하는 핵심은.. 함수의 인자로 배열 전체를 주는 것이 아닌 (행, 열, 배열길이) 세가지를 받아서 전역변수로 받아온 가장 큰 배열(arrr[][])을 계속 쪼개서 재귀함수의 인자로 넣어주는 것이다. 즉,

• isDiff() == false → len을 3으로 나누고 총 9등분된 좌표의 시작점에서 다시 조회하기

💡 코드

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

public class BOJ_1780 {
    public static int[] cnt;
    public static int[][] arrr; //<-> arr
    public static int N;

    public static boolean isDiff(int r, int c, int len) {
        int t = arrr[r][c];

        for(int i = r; i < r+len; i++) {
            for(int j = c; j < c+len; j++) {
                if(t != arrr[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void splitAndCheck(int r, int c, int len) {
        if (isDiff(r, c, len)){
            cnt[arrr[r][c]+1] += 1;
        } else{
            int newLen = len/3;

            for(int i = 0; i < 3; i++){
                for (int j = 0; j < 3; j++){
                    splitAndCheck(r + newLen*i, c + newLen*j, newLen);
                }
            }
        }
    }

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

        arrr = new int[N][N];
        cnt = new int[3];
        StringTokenizer st;

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++){
                arrr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        splitAndCheck(0, 0, N);

        System.out.println(cnt[0] + "\\n" + cnt[1] + "\\n" + cnt[2]);
    }
}

💡 정리

쿼드 트리

: 공간을 재귀적인 호출로 4개의 자식 노드로 분할하는 방법 (이 문제에서는 9개의 노드로 분할)

→ 재귀적인 호출을 통해 각 노드간의 간격이 1보다 작거나 같을 때까지 분할한다.

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

1992번: 쿼드트리

 

쓸데없는 코드 줄이기

내가 짰던 노가다 코드

    public static int cnt_minus = 0;
    public static int cnt_0 = 0;
    public static int cnt_plus = 0;

    if (arrr[r][c] == -1){
	    cnt_minus += 1;
    } else if (arrr[r][c] == 0){
	    cnt_0 += 1;
    } else {
	    cnt_plus += 1;
    }

 System.out.println(cnt_minus);
 System.out.println(cnt_0);
 System.out.println(cnt_plus);

참고한 블로그의 깔끔한 코드

public static int[] cnt;

cnt[arrr[r][c]+1] += 1;

System.out.println(cnt[0] + "\\n" + cnt[1] + "\\n" + cnt[2]);

이 부분을 보고 나는 역시 코드를 무식하게 짜는구나 싶었다.ㅎㅎ

 

 

참고

https://pangsblog.tistory.com/43