[JAVA/알고리즘] 분할 정복 알고리즘 Divide and conquer (백준 2630)

분할 정복 알고리즘이란, 

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법. 보통 재귀 함수로 구현

 

1. Divide 

원래 문제를 분할이 가능할 때까지 더 작은 하위 문제로 분할

2.  Conquer

각 하위 문제를 재귀적으로 해결

3. Combine

해결한 하위 문제들을 통합하여 원래 문제를 해결

 

장점 : Top-down 재귀방식으로 구현하여 코드가 직관적. 문제를 나누어 해결하여 병렬적으로 문제 해결

단점: 재귀 함수 호출로 오버헤드 발생할 수 있음. 스택에 많은 데이터가 보관되면 오버플로우 발생

 

---

[백준 2630] 색종이 만들기

전체 종이가 같은 색으로 칠해져 있도록 색종이의 한 변의 길이를 2로 1이 될 때까지 나누어 각 색의 색종이의 개수를 구하는 문제

 

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

public class Main {
    private static int[][] paper;
    private static int white = 0;
    private static int blue = 0;

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

        for (int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=0; j<n; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        cutPaper(0,0, n);
        System.out.println(white);
        System.out.println(blue);
    }

    private static void cutPaper(int x, int y, int len) {
        if (isOneColor(x, y, len)) {
            if (paper[y][x] == 1) blue++;
            else white++;
        }
        else {
            len = len / 2;
            cutPaper(x, y, len);
            cutPaper(x + len, y, len);
            cutPaper(x, y + len, len);
            cutPaper(x + len, y + len, len);
        }
    }

    private static boolean isOneColor (int x, int y, int len) {
        int flag = paper[y][x];
        for (int i=y; i<y + len; i++) {
            for (int j=x; j<x + len; j++) {
                if (paper[i][j] != flag) return false;
            }
        }
        return true;
    }
}

처음엔 0, 0에서 시작하여 n만큼 모두 같은 색인지 확인.

 

모두 같은 색이 아니라면 각 변을 2로 나누어 (n / 2) X (n / 2) 크기의 색종이 4개로 만들고, 각 종이가 같은 색으로 이루어져 있는지 확인.

 

각 변을 2로 나눌 때 마다, 하나의 종이는 4개의 종이로 분할되므로, 

cutPaper(x, y, len);					//제 1사분면
cutPaper(x + len, y, len);				//제 2사분면
cutPaper(x, y + len, len);				//제 3사분면
cutPaper(x + len, y + len, len);			//제 4사분면

 

위처럼 각각의 종이를 같은 색인지 재귀적으로 확인. 

 

 

---

<분할 정복 알고리즘 (재귀함수)를 사용하지 않고 반복문을 이용한 방법>

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

public class Main {
    private static int[][] paper;
    private static boolean[][] visited;
    private static int white = 0;
    private static int blue = 0;

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

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int len = n;
        while (len > 1) {
            for (int y=0; y<n; y+=len) {
                for (int x=0; x<n; x+=len) {
                    checkPaper(x, y, len);
                }
            }

            if (isAll(n)) break;
            len = len / 2;
        }

        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (!visited[i][j]) {
                    if (paper[i][j] == 1) blue++;
                    else white++;
                }
            }
        }

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

    private static void checkPaper(int x, int y, int len) {
        int flag = paper[y][x] == 1 ? 1: 0;
        for(int i=y; i<y+len; i++) {
            for(int j=x; j<x+len; j++) {
                if(visited[i][j]) return;
                if(paper[i][j] != flag) return;
            }
        }

        for(int i=y; i<y+len; i++) {
            for(int j=x; j<x+len; j++) {
                visited[i][j] = true;
            }
        }
        if (flag == 1) blue++;
        else white++;
    }

    private static boolean isAll(int n) {
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++) {
                if (!visited[i][j]) return false;
            }
        }
        return true;
    }
}

 

 

 

 

<참고자료>

https://st-lab.tistory.com/227

[백준] 2630번 : 색종이 만들기 - JAVA [자바]

https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

분할 정복 알고리즘 - 위키백과, 우리 모두의 백과사전

https://loosie.tistory.com/237

[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)