문제 분석

• N×N 크기의 정사각형 모양의 종이
• 정사각형을 이루는 각 칸은 흰색(0) or 파란색(1)
• 전체 종이가 모드 같은 색으로 칠해져 있지 않으면 가로 & 세로 방향으로 N/2을 하여 4개의 똑같은 크기의 색종이로 나눔
• 나누어진 종이에 대해서도 같은 작업을 반복하여 수행
  (하나의 정사각형 칸이 되면 더 이상 자를 수 없음)
• Q: 종이의 한 변의 길이 N과 각 정사각형칸의 색이 주어질 때
  잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하여라

입출력

8 // N
1 1 0 0 0 0 1 1 // N x N
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

문제 풀이 방법

분할 정복

1) N * N 크기의 색종이를 이차원 배열에 입력 받기
2) 종이를 자르는 함수 divide 작성 (row, col, size)

• isUniform 함수: size * size 크기의 종이가 같은 값인지 확인
  if 같은 값 -> 0 / 1 값에 따라 white / blue ++
  else: 중간 인덱스 저장 -> 다시 나누기

코드 작성

public class Main {
	static int N;
	static int[][] paper;
	static int whitePapers=0;
	static int Bluepapers=0;
	
	public static void main (String [] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// [input]
		N = Integer.parseInt(br.readLine());
		
		paper = new int[N][N];
		
		for(int i=0; i< N; i++) {
			paper [i]=Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		}
		
		// [logic]
		divide(0,0,N);
		
		
		// [output]
		System.out.println(whitePapers);
		System.out.println(Bluepapers);
		
	}

	/**
	 * check a square with given size
	 * @param row : 현재 종이의 가로 방향 시작 인덱스
	 * @param col : 현재 종이의 세로 방향 시작 인덱스
	 * @param size : 현재 종이의 크기
	 */
	private static void divide(int row, int col, int size) {
		// 종이의 각 칸이 동일한 값인지 확인
		if(isUniform(row, col,size)) {
			if(paper[row][col]==0) whitePapers ++;
			else Bluepapers ++;
			return;
		}
		
		// else
		int half = size / 2;
		// 4조각으로 자르기 & 각 조각에 대해 재귀 호출
		divide(row,col,half); // 좌상
		divide(row, col+half, half); // 우상
		divide(row+half, col, half); // 좌하
		divide(row+half,col+half,half); // 우하
	}

	// 현재 자른 종이가 모두 같은 값을 가지고 있는지 확인하는 함수
	private static boolean isUniform(int row, int col, int size) {
		int color = paper[row][col];
		for(int i=row;i<row+size;i++) {
			for(int j=col;j<col+size;j++) {
				if(paper[i][j]!=color) return false;
			}
		}
		return true;
	}
}

계산 복잡도 & 개선 방향

1. 시간복잡도 = O(N²)

• divide(row, col, size) 함수:
  isUniform()을 호출할 때, 현재 영역의 모든 칸을 검사함
• isUniform():
  영역 크기가 size × size일 때 O(size²) 시간이 걸림
  최악의 경우 모든 칸을 여러 번 검사할 수 있음

2. 공간복잡도 = O(N²)

• 입력 배열 : paper: N × N -> O(N²) 공간
• 재귀 호출 스택: 최악의 경우 종이를 계속 1x1까지 쪼개므로, 깊이가 logN 단계만큼 생김 -> O(logN)

3. 개선 방향

• Prefix Sum (2D 누적합) 구하는 방법

??? & !!!

1. divide 함수의 매개변수 (parameter)

• row, col 위치에서 시작해서 size×size 크기의 종이를 확인
• row: 현재 종이의 시작 행 인덱스
  col: 현재 종이의 열 인덱스
  size: 현재 종이 부분의 한 변의 길이
• divide(row,col,half); : 인자 (argument)로 전달

2. 각 조각에 대한 재귀 처리

• 종이가 단일 색이 아니라면, 4등분
• 4등분된 각 조각은 크기가 절반인 문제로 정의됨
  -> 좌상, 좌하, 우상, 우하의 각각 시작좌표를 다시 divide 함수의 인자로 넘겨 재귀 호출