[BOJ] 2630 색종이 만들기 - JAVA

1. 문제

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

2630번: 색종이 만들기

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

2022.02.16 - [코딩테스트/BOJ] - [BOJ] 1992 쿼드트리 - JAVA 와 비슷한 문제다.

---

2. 풀이

메인함수

• 색종이 자르는 함수를 부른 뒤 static 배열 result값을 출력한다.

static int[][] paper;
static int[] result;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;

   int N = Integer.parseInt(in.readLine());
   paper = new int[N][N];
   result = new int[2];

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

   cutPaper(0,0,N);
   System.out.print(result[0]+"\n"+result[1]);
}

색종이 자르는 함수(cutPaper)

• n==1이거나 종이가 전부 같은 숫자라면 result배열에 +1한다. 해당 숫자를 인덱스로 삼아 접근한다.
• 위의 경우가 아니라면 가로 세로 전부 반씩 쪼개서 네 가지 경우를 호출한다.

private static void cutPaper(int i, int j, int n) {
   if(n==1 || checkPaper(i,j,n)) {
      result[paper[i][j]]++;
      return;
   }

   int half = n/2;
   cutPaper(i,j,half);
   cutPaper(i+half,j,half);
   cutPaper(i,j+half,half);
   cutPaper(i+half,j+half,half);
}

자른 색종이를 체크하는 함수

• 첫번째 값을 저장하고 입력받은 인덱스+n까지 전부 돌아서 첫번째값과 다른 값이 있다면 바로 false를 리턴한다.
• 탐색 후에도 리턴되지 않았다면 true를 반환한다.

private static boolean checkPaper(int i, int j, int n){
   int check = paper[i][j];
   for(int ii=i;ii<i+n;ii++){
      for(int jj=j;jj<j+n;jj++){
         if(check!=paper[ii][jj]) return false;
      }
   }
   return true;
}

---

3. 결과