[Java] baekjoon_2630 : 색종이 만들기

분할 정복, 재귀

색종이 만들기 : Silver2

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

2630번: 색종이 만들기

 

 

 

 풀이

import java.io.*;
import java.util.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  static int[][] squares;
  static int white = 0;
  static int blue = 0;
 
  public static void main(String[] args) throws IOException {
    int N = Integer.parseInt(br.readLine());
    squares = new int[N][N];
    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int j = 0; j < N; j++) {
        squares[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    cutSquares(N, 0, 0);

    bw.write(white + "\n");
    bw.write(blue + "\n");
    bw.flush();
    br.close();
    bw.close();
  }
  
  public static void cutSquares(int size, int row, int col) throws IOException {
    if (checkColor(size, row, col)) {
      if (squares[row][col] == 0) {
        white++;
      } else {
        blue++;
      }
      return;
    }

    int half = size / 2;
    cutSquares(half, row, col); // 왼쪽 위
    cutSquares(half, row, col + half); // 오른쪽 위
    cutSquares(half, row + half, col); // 왼쪽 아래
    cutSquares(half, row + half, col + half); // 오른쪽 아래
  }

  private static boolean checkColor(int size, int row, int col) {
    for (int i = row; i < row + size; i++) {
      for (int j = col; j < col + size; j++) {
        if (squares[i][j] != squares[row][col]) {
          return false;
        }
      }
    }
    return true;
  }
}

 

ㄴ 첫 번째로 정사각형 모양의 종이의 한 변의 길이 N을 입력 받는다.
ㄴ 그 다음으로 N개의 줄에 걸쳐서 각 정사각형의 색상 정보를 입력 받는다. 

ㄴ 여기서 0은 하얀색, 1은 파란색을 의미한다.

 

ㄴ cutSquares 메서드는 재귀적으로 호출되며, 주어진 종이를 분할하면서 하얀색 색종이와 파란색 색종이의 개수를 세는 역할을 한다.

ㄴ 입력으로 받은 size는 현재 종이의 한 변의 길이를 나타낸다.
ㄴ row와 col은 현재 종이의 왼쪽 위 모서리의 좌표를 나타낸다.

ㄴ checkColor 메서드를 호출하여 현재 종이가 모두 같은 색으로 칠해져 있는지 확인한다.
ㄴ 모두 같은 색이라면 해당 색종이의 개수를 증가시키고 종료하도록 했다.
ㄴ 마지막으로 같은 색이 아니라면 현재 종이를 4등분하여 각각의 작은 종이에 대해 같은 과정을 반복하도록 했다..

 

ㄴ checkColor 메서드는 주어진 정사각형의 색이 모두 같은지를 확인하는 역할을 한다.
ㄴ size, row, col을 사용하여 주어진 정사각형 범위 내의 모든 정사각형이 같은 색인지 확인한다.
ㄴ 만약 모든 정사각형의 색이 같다면 true를 반환하고, 그렇지 않다면 false를 반환한다.

 

=> 이러한 과정을 통해 주어진 종이를 분할하면서 하얀색 색종이와 파란색 색종이의 개수를 세고, 그 결과를 출력하도록 했다.