문제

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

풀이

먼저 경우의 수가 3가지로 나뉜다.

1. 구간이 잘못 나눠진 경우
2. 구간이 잘 나눠진 경우
3. 더 나눠봐야 하는 경우

나눠봐야 하는 경우에는 불순물이 있는 라인만 경계선으로 나눌 수 있으므로 불순물이 있는 곳까지 찾은 다음, 가로 또는 세로에 보석이 없는지 체크한다.

가로로 한번 나눠보고, 세로로 한번 나눠본다. 둘 다 가능하다면 가로 세로 모두 구간을 각각 나눠서 결과값을 가져온다. 가로로 나눈다면 위, 아래로 구간이 생기고 세로로 나눈다면 왼쪽, 오른쪽으로 구간이 생긴다.

import javax.print.attribute.standard.PresentationDirection;
import java.util.Scanner;

public class Num2339 {

    public static int N;
    public static int Num[][];

    public static void main(String[] args) {
        //input
        Scanner scanner = new Scanner(System.in);
        N = Integer.parseInt(scanner.nextLine());
        Num = new int[N][N];
        for (int i=0; i<N; i++) {
            String[] a = scanner.nextLine().split(" ");
            for (int j=0; j<N; j++) {
                Num[i][j] = Integer.parseInt(a[j]);
            }
        }

        //logic
        int answer = input(0, N, 0, N, -1);

        //output
        if (answer == 0)
            System.out.println(-1);
        else
            System.out.println(answer);
    }

    public static int input(int startHeight, int endHeight, int startWidth, int endWidth, int cut) {
        int answer = 0;
        int voSuck = 0;
        int bollSoon = 0;
        for (int i=startHeight; i < endHeight; i++) {
            for (int j=startWidth; j < endWidth; j++) {
                if (Num[i][j] == 1)
                    bollSoon++;
                else if (Num[i][j] == 2)
                    voSuck++;
            }
        }
        if (voSuck == 0 || (voSuck == 1 && bollSoon >= 1) || (voSuck >=2 && bollSoon == 0))
            return 0;
        else if (voSuck == 1 && bollSoon == 0)
            return 1;
        else {
            for (int i=startHeight; i < endHeight; i++) {
                for (int j=startWidth; j < endWidth; j++) {
                    if (Num[i][j] == 1) {
                        if (cut != 0) {
                            boolean signal = true;
                            for (int k = startWidth; k < endWidth; k++) {
                                if (Num[i][k] == 2) {
                                    signal = false;
                                    break;
                                }
                            }
                            if (signal == true) {
                                int first = input(startHeight, i, startWidth, endWidth, 0);
                                int second = input(i + 1, endHeight, startWidth, endWidth, 0);
                                answer += first * second;
                            }
                        }
                        if (cut != 1) {
                            boolean signal = true;
                            signal = true;
                            for (int k = startHeight; k < endHeight; k++) {
                                if (Num[k][j] == 2) {
                                    signal = false;
                                    break;
                                }
                            }
                            if (signal == true) {
                                int first = input(startHeight, endHeight, startWidth, j, 1);
                                int second = input(startHeight, endHeight, j + 1, endWidth, 1);
                                answer += first * second;
                            }
                        }
                    }
                }
            }
        }
        return answer;
    }
}