분할 정복(2630, 1992)

[색종이 만들기 _ 2630]

 

 

* 조건

1. 전체 색종이의 크기 n(2의 배수)이 주어진다
2. 하얀색(0)과 파란색(1)이 배열 값으로 주어진다
3. 전체 종이가 같은색으로 이루어져있지 않으면 n/2만큼 가로 세로로 자른다(4등분) 
4. 잘린 영역 내에서 같은 색으로 이루어져 있다면 그 부분은 안잘라도 된다
5. 자른 영역이 한 칸이 될 때까지 반복한다
6. 최종적으로 잘린 하얀색과 파란색의 색종이 개수를 출력한다

 

 

* 알고리즘

• 분할 정복

 

 

* 로직

• 현재 사이즈에서 모두 같은 색상으로 이루어져있는지 확인
• 같은 색상이라면 하얀색 또는 파란색의 카운트를 하나 늘림
• 만약 같지 않다면 사이즈를 n/2를 적용시킨 후, 4분할된 영역을 한군데씩 다시 탐색
• 이를 반복한다

 

import java.util.Scanner;

public class Problem_2630 {

    static int[][] map;
    static int white = 0;
    static int blue = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        map = new int[n][n];

        for(int i = 0; i< n; ++i){
            for(int j = 0; j< n; ++j){
                map[i][j] = scanner.nextInt();
            }
        }

        //같은 색들로 존재하는지 확인 -> 아니라면 분할
        doProcess(n, 0, 0);

        System.out.println(white);
        System.out.println(blue);
    }

    private static void doProcess(int n, int front, int rear) {
        if(findSameColor(n, front, rear)){
            if(map[front][rear] == 0) white++;
            else blue++;

            return;
        }

        //같은 색이 아니라면
        doProcess(n/2, front, rear);
        doProcess(n/2, front, rear + (n/2));
        doProcess(n/2, front + (n/2), rear);
        doProcess(n/2, front + (n/2), rear + (n/2));
    }

    private static boolean findSameColor(int n, int front, int rear) {
        int tmp = map[front][rear];
        for(int i=front; i<front+n; ++i){
            for(int j=rear; j<rear+n; ++j){
                if(tmp == map[i][j]) tmp = map[i][j];
                else return false;
            }
        }

        return true;
    }
}

 

 

[쿼드 트리 _ 1992]

 

 

* 조건

1. 배열의 사이즈 N이 주어진다
2. 배열에 흰점 0, 검은점 1이 주어진다
3. 만약 해당 사이즈에서 같은 색상이 존재하면 해당 색상 값으로 압축한다
4. 만약 같은 색상이 아니라면 사이즈를 n/2를 하여 4등분 한 뒤, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 같은 색상인지를 탐색한다
5. 압축된 결과를 출력한다

 

 

* 알고리즘

• 분할 정복

 

 

* 로직

• 현재 사이즈에서 모두 같은 색인지 판별한다
• 만약 같은 색이라면 해당 색상의 값을 리스트에 추가하고 해당 재귀를 종료한다
• 해당 사이즈에서 색이 같지 않다면 "(" 괄호를 추가한다
• 사이즈를 n/2로 한 뒤, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 탐색한다
• 위 4가지 방향을 다 탐색했다면(해당 사이즈 내에서 4방향으로 탐색완료) -> ")" 괄호를 추가한다

 

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

public class Problem_1992 {

    static ArrayList<String> arrayList = new ArrayList<>();
    static int[][] map;

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

        for(int i=0; i<n; ++i){
            String input = br.readLine();
            for(int j=0; j<n; ++j){
                map[i][j] = Integer.parseInt(input.substring(j, j+1));
            }
        }

        doProcess(n, 0, 0);
        for(String ans : arrayList)
            System.out.print(ans);
    }

    private static void doProcess(int n, int front, int rear) {
        //같은지 탐색 -> 같지 않다면 분할
        if(findSameColor(n, front, rear)){
            if(map[front][rear] == 0) arrayList.add("0");
            else arrayList.add("1");

            return;
        }

        //색이 다르다면 "(" 추가
        arrayList.add("(");

        doProcess(n/2, front, rear);
        doProcess(n/2, front, rear + (n/2));
        doProcess(n/2, front + (n/2), rear);
        doProcess(n/2, front + (n/2), rear + (n/2));

        //n에 대한 사이클이 끝나면 ")" 추가
        arrayList.add(")");
    }

    private static boolean findSameColor(int n, int front, int rear) {
        int tmp = map[front][rear];
        for(int i=front; i<front+n; ++i){
            for(int j=rear; j<rear+n; ++j){
                if(tmp == map[i][j]) tmp = map[i][j];
                else return false;
            }
        }
        return true;
    }
}

 

 

사이즈를 분할할 때 경우를 차분하게 생각하는 습관이 필요하다는 것을 느꼈다. 또한 재귀로 넘겨주는 매개 변수의 경계값들을 어떤 식으로 넘길지를 찾는게 핵심인 것 같다. 앞으로도 분할 정복의 경우, 이를 먼저 생각해야겠다.