[Algorithm/Kotlin] 백준 2630번 색종이 만들기: 분할정복을 활용한 풀이법

1. 문제 설명

주어진 N × N 크기의 색종이가 하얀색(0)과 파란색(1) 으로 칠해져 있을 때,
이를 모두 같은 색이 될 때까지 잘라 각 색상의 개수를 구하는 문제입니다.

문제 조건

1. N은 2^k (k = 1~7) 형태로 주어집니다. (즉, 2, 4, 8, 16, 32, 64, 128 중 하나)
2. 색종이가 한 가지 색으로만 칠해져 있다면, 더 이상 자르지 않고 해당 색종이 개수를 증가시킵니다.
3. 혼합된 색상이 있다면, 정사각형을 4등분하여 동일한 방식으로 재귀적으로 처리합니다.

예제 입력

8
1 1 0 0 0 0 1 1
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

예제 출력

9
7

 

즉, 하얀색 색종이가 9개, 파란색 색종이가 7개가 만들어집니다.

---

2. 문제 해결 아이디어 (분할 정복)

1. 현재 영역이 모두 같은 색인지 확인

• (row, column, size) 영역이 모두 같은 색인지 검사하는 함수 isUniform(row, column, size)를 구현합니다.
• 모든 칸이 같은 값이라면 whiteCount++ 또는 blueCount++ 를 증가시키고 종료합니다.

2. 색상이 다르면 4등분하여 재귀 호출

• 색상이 섞여 있으면, size를 절반(size / 2)으로 줄여 4개의 작은 영역으로 분할하여 divide()를 재귀 호출합니다.
  
  

  구역	재귀 호출
  좌상 (왼쪽 위)	divide(row, column, newSize)
  우상 (오른쪽 위)	divide(row, column + newSize, newSize)
  좌하 (왼쪽 아래)	divide(row + newSize, column, newSize)
  우하 (오른쪽 아래)	divide(row + newSize, column + newSize, newSize)

---

3. 구현 코드

import java.io.*

lateinit var paper: Array<IntArray>
var whiteCount = 0
var blueCount = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    paper = Array(N) { br.readLine().split(" ").map { it.toInt() }.toIntArray() }

    divide(0, 0, N) // 초기 전체 영역을 탐색

    println(whiteCount)
    println(blueCount)
}

// 현재 영역이 모두 같은 색인지 확인하는 함수
private fun isUniform(row: Int, column: Int, size: Int): Boolean {
    val firstColor = paper[row][column]
    for (i in row until row + size) {
        for (j in column until column + size) {
            if (paper[i][j] != firstColor) return false
        }
    }
    return true
}

// 4등분하여 재귀적으로 탐색하는 함수
private fun divide(row: Int, column: Int, size: Int) {
    if (isUniform(row, column, size)) { // 같은 색이면 개수 증가 후 종료
        if (paper[row][column] == 0) whiteCount++ else blueCount++
        return
    }

    val newSize = size / 2
    divide(row, column, newSize)                   // 왼쪽 위
    divide(row, column + newSize, newSize)         // 오른쪽 위
    divide(row + newSize, column, newSize)         // 왼쪽 아래
    divide(row + newSize, column + newSize, newSize) // 오른쪽 아래
}

---

4. 시간 복잡도 분석

1. 최악의 경우

• 한 변의 길이가 128(= 2^7)인 경우, 최대 7번 분할 가능
• 각 분할마다 4개의 새로운 영역이 생성되므로, 재귀 깊이는 O(log N)
• 각 isUniform() 함수에서 size × size만큼 순회하므로 최악의 경우 O(N²)
• 결론: O(N²)

2. 현실적인 시간 복잡도

• 대부분의 경우, isUniform()에서 빠르게 종료되므로 실제 연산량은 훨씬 적습니다.
• N=128까지도 충분히 실행 가능합니다.

---

5. 사용한 자료구조

자료구조	사용 목적
Array<IntArray>	색종이 정보를 저장하기 위한 2D 배열
Recursive Function	분할 정복을 통한 문제 해결

---

6. 최종 정리

항목	내용
알고리즘 유형	분할 정복 (Divide & Conquer)
시간 복잡도	O(N²), 하지만 isUniform()이 빠르게 종료되는 경우 연산량 감소
자료구조	2D 배열 (Array<IntArray>) + 재귀 호출
핵심 아이디어	1️⃣ 모든 영역이 같은 색인지 검사 → 2️⃣ 다르면 4등분하여 재귀 호출

---

문제링크: https://www.acmicpc.net/problem/2630