https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
- 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.
- 전체 종이의 크기가 N*N(N=2^k, k는 1이상 7이하의 자연수)이라면 종이를 자르는 규칙은 다음과 같다,
- 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 아래 그림과 같이 똑같은 크기의 네 개의 N/2*N/2 색종이로 나눈다.
- 나누어진 종이 1,2,3,4 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다.
- 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
- 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램
- N = 전체 종이의 한 변의 길이, N은 2,4,8,16,32,64,128 중 하나
- 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어짐
문제 풀이
분할 정복 알고리즘
- 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
1) DIvide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.
2) Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.
3) Combine : Conquer한 문제들을 통합하여 원래의 문제의 답을 얻는다.
[백준] 2630번 : 색종이 만들기 - JAVA [자바] (tistory.com)
[백준] 2630번 : 색종이 만들기 - JAVA [자바]
www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차
st-lab.tistory.com
1) 각각의 행과 열의 시작점(초기는 (0,0)이 기준)에서 현재 파티션에 대하여 모두 같은 색상인지 체크를 먼저 해야 함
2) 색상이 같다면 해당 색상의 개수를 1 증가 시키고 함수를 종료 한다.
3) 색상이 같지 않다면, 4등분 하여 각 부분 문제로 쪼개어 문제를 푼다.
정답
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
static int cnt_w = 0;
static int cnt_b = 0;
static int board[][];
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
board = new int[n][n];
for(int i=0; i<n; i++)
{
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++)
{
board[i][j] = Integer.parseInt(st.nextToken());
}
}
partition(0,0,n);
bw.write(cnt_w+"");
bw.newLine();
bw.write(cnt_b+"");
bw.flush();
bw.close();
}
//색종이의 색이 다를 경우 변의 길이를 자름
static void partition(int row, int col, int size)
{
//색이 같을 경우는 각 카운트 증가
if(check(row,col,size))
{
if(board[row][col]==0)
{
cnt_w++;
}
else
{
cnt_b++;
}
return;
}
//색이 다를 경우
int newSize = size/2; //절반
//재귀 호출
partition(row,col,newSize); //2사분면
partition(row,col+newSize,newSize); //1사분면
partition(row+newSize,col,newSize); //3사분면
partition(row+newSize,col+newSize, newSize); //4사분면
}
//색종이의 색이 같은지 다른지 확인
static boolean check(int row, int col, int size)
{
int color = board[row][col]; //첫 번째 원소를 기준으로 검사
for(int i=row; i<row+size; i++)
{
for(int j=col; j<col+size; j++)
{
//색상이 같지 않다면 false를 리턴
if(board[i][j] != color)
{
return false;
}
}
}
//검사가 모두 통과했다는 의미이므로 true 리턴
return true;
}
}
'Java > 백준' 카테고리의 다른 글
[JAVA] 백준 1790 종이의 개수 (0) | 2024.03.06 |
---|---|
[JAVA] 백준 1992 쿼드 트리 (1) | 2024.03.06 |
[JAVA] 백준 13305 주유소 (1) | 2024.03.04 |
[JAVA] 백준 1541 잃어버린 괄호 (0) | 2024.03.04 |
[JAVA] 백준 11399 ATM (0) | 2024.03.04 |