[알고리즘] 백준 2630 색종이 만들기 -분할 정복- 자바

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

 

백준 단계별 풀기의 분할 정복 첫번째 문제입니다. 

이전에 프로그래머스에서 푼 문제와 거의 똑같은 문제라고 볼 수 있습니다.

youngest-programming.tistory.com/400

[알고리즘] 프로그래머스 쿼드압축 후 개수 세기 (월드 코드 챌린지 시즌 1) -dfs, 백트랙킹- 자바

 

 

[Java]

import java.util.Scanner;

public class Main {
    private static int[][] map;
    private static int zeroWhite = 0;
    private static int oneBlue = 0;

    private static void dfs(int n, int x, int y) {
        if (n == 1) {
            if (map[x][y] == 1) {
                oneBlue++;
            } else {
                zeroWhite++;
            }
            return;
        }
        if (isSame(n, x, y)) {
            return;
        }
        dfs(n / 2, x, y);
        dfs(n / 2, x + n / 2, y);
        dfs(n / 2, x, y + n / 2);
        dfs(n / 2, x + n / 2, y + n / 2);
    }

    public static boolean isSame(int n, int x, int y) {
        int first = map[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (first != map[i][j]) {
                    return false;
                }
            }
        }
        //해당 종이 하나로 퉁쳐서 +1
        if (first == 0) {
            zeroWhite += 1;
        } else {
            oneBlue += 1;
        }
        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(zeroWhite);
        System.out.println(oneBlue);
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. :)