[알고리즘] 백준 1780 종이의 개수 -분할정복- 자바 코틀린

www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

 

 

백준 분할정복 단계별풀기 3단계 문제입니다. 

이전에 푼것들과 동일한데 이번에는 4등분이 아닌 9등분을 합니다.

기존 4번 분할하던것을 9분할로만 변경하면 해결됩니다.

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

public class Main {
    private static int[][] map;
    private static int zero = 0;
    private static int one = 0;
    private static int minus1 = 0;

    private static void dfs(int n, int x, int y) {
        if (n == 1) {
            int num = map[y][x];
            if (num == -1) {
                minus1++;
            } else if (num == 0) {
                zero++;
            } else {
                one++;
            }
            return;
        }
        if (isSame(n, x, y)) {
            return;
        }
        dfs(n / 3, x, y);
        dfs(n / 3, x + n / 3, y);
        dfs(n / 3, x + 2 * n / 3, y);
        dfs(n / 3, x, y + n / 3);
        dfs(n / 3, x, y + 2 * n / 3);
        dfs(n / 3, x + n / 3, y + n / 3);
        dfs(n / 3, x + n / 3, y + 2 * n / 3);
        dfs(n / 3, x + 2 * n / 3, y + n / 3);
        dfs(n / 3, x + 2 * n / 3, y + 2 * n / 3);
    }

    private static boolean isSame(int n, int x, int y) {
        int first = map[y][x];
        for (int i = y; i < y + n; i++) {
            for (int j = x; j < x + n; j++) {
                if (first != map[i][j]) {
                    return false;
                }
            }
        }
        //해당 종이 하나로 압축
        if (first == 0) {
            zero++;
        } else if (first == 1) {
            one++;
        } else {
            minus1++;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        map = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        dfs(size, 0, 0);
        System.out.println(minus1);
        System.out.println(zero);
        System.out.println(one);
    }
}

 

[Kotlin]

import java.util.*

private lateinit var map: Array<IntArray>
private var zero = 0
private var one = 0
private var minus1 = 0

private fun dfs(n: Int, x: Int, y: Int) {
    if (n == 1) {
        when (map[y][x]) {
            -1 -> {
                minus1++
            }
            0 -> {
                zero++
            }
            else -> {
                one++
            }
        }
        return
    }
    if (isSame(n, x, y)) {
        return
    }
    dfs(n / 3, x, y)
    dfs(n / 3, x + n / 3, y)
    dfs(n / 3, x + 2 * n / 3, y)
    dfs(n / 3, x, y + n / 3)
    dfs(n / 3, x, y + 2 * n / 3)
    dfs(n / 3, x + n / 3, y + n / 3)
    dfs(n / 3, x + n / 3, y + 2 * n / 3)
    dfs(n / 3, x + 2 * n / 3, y + n / 3)
    dfs(n / 3, x + 2 * n / 3, y + 2 * n / 3)
}

private fun isSame(n: Int, x: Int, y: Int): Boolean {
    val first = map[y][x]
    for (i in y until y + n) {
        for (j in x until x + n) {
            if (first != map[i][j]) {
                return false
            }
        }
    }
    //해당 종이 하나로 압축
    when (first) {
        0 -> {
            zero++
        }
        1 -> {
            one++
        }
        else -> {
            minus1++
        }
    }
    return true
}

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val size = sc.nextInt()
    map = Array(size) { IntArray(size) }
    for (i in 0 until size) {
        for (j in 0 until size) {
            map[i][j] = sc.nextInt()
        }
    }
    dfs(size, 0, 0)
    println(minus1)
    println(zero)
    println(one)
}