- 문제 :
https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
- 분류 : 분할정복 알고리즘
기본적인 분할정복 알고리즘 문제이다.
첨에 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++;
}
}
}'알고리즘 > 백준' 카테고리의 다른 글
| [백준/java] 18259번 - 큐2 (0) | 2023.05.12 |
|---|---|
| [백준/java] 2164번 - 카드2 (0) | 2023.05.12 |
| [백준/java] 4949번 : 균형잡힌 세상 (0) | 2023.05.12 |
| [백준/java] 9095번 - 1,2,3 더하기 (0) | 2023.05.12 |
| [프로그래머스/java] 2018 카카오 블라인드 1차 캐시 & LRU 알고리즘 (0) | 2023.05.12 |
