백준, 종이의 개수(1780, java)

문제 설명

NxN 크기의 종이가 있고 각 칸에는 -1, 0, 1로 표시가 되어 있다. 같은 숫자가 표시되어 있는 영역을 하나의 종이로 보는데, 만일 숫자가 모두 같지 않다면 해당 종이를 9등분 한 다음 9등분 한 영역을 다시 확인한다.

 

결과적으로 -1로만 채워진 종이의 수, 0으로만 채워진 종이의 수, 1로만 채워진 종이의 수를 구하여라.

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

1780번: 종이의 개수

문제 풀이

분할 정복 문제로 나는 재귀를 이용하여 풀었다. 

일단 간단하게 푸는 방법을 설명하겠다.

1. 먼저 주어진 영역을 확인하면서 숫자가 모두 같은지 본다.

2. 숫자가 같으면 해당 숫자의 종이 수를 하나 올려준다.

3. 같지 않다면 해당 영역을 9등분 한 뒤, 9등분 한 영역을 첫 번째부터 차례대로 1번을 실행한다.

 

과정

먼저 주어진 행렬을 보자. 해당 행렬은 전부 같은 수로 이루어져 있지 않으므로 9등분을 해줘야 한다. 참고로 말하자면 9등분을 할 때 나눠진 종이의 크기는 모두 같아야 한다.

그리고 나눠진 9개의 구역 중 제일 첫 번째를 확인한다.

아래는 나눈 부분을 확인하는 코드이다. 보면 범위를 시작 좌표부터 +n까지 해준 것을 알 수 있다. 여기서 n이란 나눈 부분의 가로, 세로 길이로 이전 영역의 /3이라고 볼 수 있다.

    public static boolean check(int startR, int startC, int n) {
        int start = map[startR][startC];

        for (int i=startR; i<startR + n; i++) {
            for (int j=startC; j<startC+n; j++) {
                if (map[i][j] != start) {
                    return false;
                }
            }
        }
        return true;
    }

영역이 0으로 전부 동일하므로 다음 영역을 확인한다. 다음 영역 또한 1로 전부 동일한 것을 알 수 있다.

이렇게 확인하다가 7번째 부분은 같은 수로 이루어져 있지 않다는 것을 알 수 있다.

7번째 구역을 동일하게 9등분으로 구역을 나눈다.

그리고 또 9 등분한 구역을 위의 check() 메서드로 확인한다. 어차피 숫자는 하나라 많이 볼 필요는 없지만

 

 

재귀

이렇게 위의 과정을 재귀로 표현해주면 된다. 재귀로 표현할 때는 if - else 구문을 쓰면 편한데, if 문에는 check()가 참이라 해당 구역에 숫자가 모두 같다는 조건을 넣어준다. if 조건에 걸리면 해당 숫자가 무엇인지 확인해서 answer의 구역에 숫자를 하나 올려주면 된다.

 

만일 check()가 거짓이라면 구역의 숫자가 모두 같지 않다는 의미이니 해당 구역을 9등분 한다. 등분을 할 때는 반복문을 쓰고 등분한 각 구역을 재귀로 탐색한다.

 

참고로 9등분할 때 반복문의 범위를 신경써줘야 한다. 조건은 현재 메서드(재귀에서 제일 나중에 들어온 메서드. 참고로 java에서는 메서드가 스택 방식으로 저장이 된다)의 r과 c부터 r+n, c+n 까지이다. 왜냐하면 n이 해당 영역의 최대 길이이기 때문이다. 그리고 i와 j를 하나씩 올려줄 때는 9등분 해줘야 하므로 n/3을 더해준다.

코드

java

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

class Pair {
    int row;
    int col;

    Pair(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {

    public static int N;
    public static int[][] map;
    public static int[] answer;

    public static boolean check(int startR, int startC, int n) {
        int start = map[startR][startC];

        for (int i=startR; i<startR + n; i++) {
            for (int j=startC; j<startC+n; j++) {
                if (map[i][j] != start) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void dfs(int r, int c, int n) {

        if (check(r, c, n)) {
            if (map[r][c] == -1) {
                answer[0]++;
            } else if(map[r][c] == 0) {
                answer[1]++;
            } else {
                answer[2]++;
            }
            return;
        } else {
            for (int i=r; i<r+n; i+=n/3) {
                for (int j=c; j<c+n; j+=n/3) {
                    dfs(i, j, n/3);
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        map = new int[N][N];
        answer = new int[3];
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 0, N);

        for(int a : answer) {
            System.out.println(a);
        }

    }

}