[백준/java] 2630번 - 색종이 만들기

- 문제 :

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

2630번: 색종이 만들기

- 분류 : 분할정복 알고리즘

 

---

기본적인 분할정복 알고리즘 문제이다.

 

첨에 2차원 배열을 어떻게 사분할로 쪼개지? 에서 조금 생각을 했는데 결국은 시작점을 상하좌우로 이동시켜서 생각하면 된다. 예를 들면 이렇다.

  //같은 색이 아니라면 1/4로 쪼갠다
int divide = n/2;

int [][] arr1 = new int[divide][divide];
int [][] arr2 = new int[divide][divide];
int [][] arr3 = new int[divide][divide];
int [][] arr4 = new int[divide][divide];


for(int i = 0; i<divide; i++) {
   for(int j = 0; j<divide; j++) {
       arr1[i][j] = arr[i][j];
       arr2[i][j] = arr[i+divide][j];
       arr3[i][j] = arr[i][j+divide];
       arr4[i][j] = arr[i+divide][j+divide];
   }
}

 

풀이

첨에 arr 배열 전체를 넘겨주는 방식으로 풀었는데 다른 사람들의 풀이를 보니 arr[][]을 static으로 두고, index만 넘겨서 푸는 방식으로 풀었길래 나도 그와 같은 방식으로 다시 풀어보았다. 

 

분할정복 알고리즘은 문제를 작은 방식으로 분할하여 해결하는 방식으로, 

이 문제는 "전체 종이 색깔이 같지 않으면 계속 쪼개는(divide)" 방식으로 해결한다. 전체 종이 색깔이 같아질 때 conquer된다.

첫번째 풀이

import java.util.*;

public class Main
{
    static int white = 0;
	static int blue = 0; 
	
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	  
	    int n = sc.nextInt();
	    int arr[][] = new int[n][n];
	    
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	            arr[i][j] = sc.nextInt();
	        }
	        sc.nextLine();
	    }
	   
	    quad(arr);
	    
	    System.out.println(white);
	    System.out.println(blue);
	}
	
	 static void quad(int[][] arr) {
	    int n = arr[0].length;
	    
	    //전체가 같은 색이면 컬러 체크
	    if(n == 1 || isAllColorSame(arr)) {
	        checkColor(arr[0][0]);
	        return;
	    }
	   
        //같은 색이 아니라면 1/4로 쪼갠다
	    int divide = n/2;
	    
        int [][] arr1 = new int[divide][divide];
        int [][] arr2 = new int[divide][divide];
        int [][] arr3 = new int[divide][divide];
        int [][] arr4 = new int[divide][divide];
        
      
	    for(int i = 0; i<divide; i++) {
	       for(int j = 0; j<divide; j++) {
	           arr1[i][j] = arr[i][j];
	           arr2[i][j] = arr[i+divide][j];
	           arr3[i][j] = arr[i][j+divide];
	           arr4[i][j] = arr[i+divide][j+divide];
	       }
	    }
	    
	    quad(arr1);
	    quad(arr2);
	    quad(arr3);
	    quad(arr4);
	}
	
	
	 static boolean isAllColorSame(int[][] arr) {
	    int color = arr[0][0];
	    int n = arr[0].length;
	    
	    //전체가 같은 색인지 체크한다
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	           if(color != arr[i][j]) {
	               return false;
	           }
	        }
	    }
	    return true;
	}
	
	static void checkColor(int color) {
       if(color == 0) {
            white++;
        } else {
            blue++;
        }
	}
}

 

두번째 풀이

import java.util.*;

public class Main
{
    static int white = 0;
	static int blue = 0; 
	static int arr[][];
	
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	  
	    int n = sc.nextInt();
	    arr = new int[n][n];
	    
	    for(int i = 0; i<n; i++) {
	        for(int j = 0; j<n; j++) {
	            arr[i][j] = sc.nextInt();
	        }
	        sc.nextLine();
	    }
	   
	    quad(n, 0, 0);
	    
	    System.out.println(white);
	    System.out.println(blue);
	}
	
	 static void quad(int n, int row, int column) {
	    
	    // 1. 전체가 같은 색이면 컬러 체크
	    if(n == 1 || isAllColorSame(n, row, column)) {
	        checkColor(arr[row][column]);
	        return;
	    }
	   
        // 2. 같은 색이 아니라면 1/4로 쪼갠다
	   int divide = n/2;
	    
       quad(divide, row, column);
       quad(divide, row+divide, column);
       quad(divide, row, column+divide);
       quad(divide, row+divide, column+divide);
	}
	
	
	//전체가 같은 색인지 체크
	 static boolean isAllColorSame(int n, int row, int column) {
	   int color = arr[row][column];
	   
	    for(int i = row; i<n+row; i++) {
	        for(int j = column; j<n+column; j++) {
	           if(color != arr[i][j]) {
	               return false;
	           }
	        }
	    }
	    return true;
	}
	
	static void checkColor(int color) {
       if(color == 0) {
            white++;
        } else {
            blue++;
        }
	}
}