[BOJ][Python] 2630 색종이 만들기 / 분할정복, 재귀

Overview

• 체감 난이도: ★★★☆☆
• 문제 레벨: 실버 2
• 문제 유형: 분할정복, 재귀
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

이미지 클릭 시 문제로 이동

예시: 8x8 종이의 경우

1단계: 8x8 전체 확인
↓ 다른 색 발견
2단계: 4x4로 4등분
↓ 각 부분 확인
3단계: 필요한 부분만 2x2로 분할
↓ 각 부분 확인
4단계: 필요한 부분만 1x1로 분할

[코드]

분할 정복(Divide and Conquer) 

1. 분할(Divide)

• 원래 문제를 더 작은 하위 문제들로 나눈다. 
• 각 하위 문제는 원래 문제와 같은 성격을 가진다. 
• 보통 원 문제의 크기를 절반으로 나누는 경우가 많다. 

2. 정복(Conquer)

• 나눈 하위 문제들을 재귀적으로 해결한다. 
• 하위 문제가 충분히 작아지면 직접 해결한다. 
• 작은 문제들의 해답을 구한다. 

3. 결합(Combine)

• 하위 문제들의 해답을 합쳐서 원래 문제의 해답을 만든다. 
• 필요한 경우 추가적인 작업을 수행한다. 

* 병합 정렬(Merge Sort)

def merge_sort(arr):
    if len(arr) <= 1:  # 기저 조건
        return arr
        
    # 분할
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # 정복 (재귀적으로 정렬)
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 결합 (병합)
    return merge(left, right)

 

* 퀵 정렬(Quick Sort)

def quick_sort(arr):
    if len(arr) <= 1:  # 기저 조건
        return arr
        
    # 분할
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    # 정복 및 결합
    return quick_sort(left) + middle + quick_sort(right)

 

장점 - 복잡한 문제 단순화, 병렬 처리 적합, 캐시 효율성 좋음

단점 - 재귀 호출로 인한 오버헤드, 메모리 사용량이 증가, 문제를 분할 가능한 형태로 만들어야 함

 

 

구현 시 중요한 생각 과정

• 입력 처리 
  • N과 색종이 정보를 어떻게 저장할까? >> 2차원 리스트가 적합

* 파라미터 결정 과정

# 1. 함수의 목적 정의
# - 특정 영역의 색종이를 확인하고 개수 세기

# 2. 필수 정보 나열
# - 어느 위치부터 봐야 하는가? → x, y 필요
# - 얼마나 큰 영역을 볼 것인가? → n 필요
# - 색종이 정보는 어디있는가? → paper 필요
# - 결과를 어디에 저장하는가? → result 필요

# 3. 초기 호출 값 결정
divide_paper(
    0,        # x: 처음 시작은 왼쪽 위부터
    0,        # y: 처음 시작은 왼쪽 위부터
    N,        # n: 처음은 전체 크기
    paper,    # paper: 입력받은 색종이 정보
    result    # result: 결과 저장할 리스트
)

 

• 색상 체크 함수
  • 어떤 정보가 필요한지? >> 시작 위치 (x, y)와 크기(n) 필요 
  • 모두 같은 색인지 어떻게 확인하지? 

def check_color(x, y, n, paper):
    color = paper[x][y]  # 첫 번째 칸의 색을 기준으로 잡음
    
    # 해당 영역의 모든 칸을 검사
    for i in range(x, x + n):
        for j in range(y, y + n):
            if paper[i][j] != color:  # 다른 색이 발견되면
                return -1  # -1 반환
    return color  # 모든 칸이 같은 색이면 해당 색상 반환

 

• 분할 정복 함수 
  • 언제 멈춰야 하지? (종료 조건)
  • 어떻게 4등분 할까? (분할 방법)
  • 결과를 어떻게 합칠까? (결과 처리)

def divide_paper(x, y, n, paper, result):
    # 현재 영역이 모두 같은 색인지 검사
    color = check_color(x, y, n, paper)
    
    if color != -1:  # 모두 같은 색이면
        result[color] += 1  # 해당 색상의 색종이 개수 증가
        return
    
    # 4등분으로 나누기
    new_n = n // 2
    # 왼쪽 위 사분면
    divide_paper(x, y, new_n, paper, result)
    # 오른쪽 위 사분면
    divide_paper(x, y + new_n, new_n, paper, result)
    # 왼쪽 아래 사분면
    divide_paper(x + new_n, y, new_n, paper, result)
    # 오른쪽 아래 사분면
    divide_paper(x + new_n, y + new_n, new_n, paper, result)

• 결과 처리
  • 각 색상의 개수를 어떻게 셀까? >> 리스트로 카운트하면 편할 것 같다. 

 

[전체 코드]

def check_color(x, y, n, paper):
    # 해당 영역의 첫 번째 색상
    color = paper[x][y]
    
    # 영역 내 모든 색상이 같은지 확인
    for i in range(x, x + n):
        for j in range(y, y + n):
            if paper[i][j] != color:
                return -1
    return color

def divide_paper(x, y, n, paper, result):
    # 현재 영역의 색상 확인
    color = check_color(x, y, n, paper)
    
    # 모든 칸이 같은 색인 경우
    if color != -1:
        result[color] += 1
        return
    
    # 4등분으로 나누어 재귀 호출
    new_n = n // 2
    divide_paper(x, y, new_n, paper, result)  # 왼쪽 위
    divide_paper(x, y + new_n, new_n, paper, result)  # 오른쪽 위
    divide_paper(x + new_n, y, new_n, paper, result)  # 왼쪽 아래
    divide_paper(x + new_n, y + new_n, new_n, paper, result)  # 오른쪽 아래

# 입력 받기
N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]

# 흰색(0)과 파란색(1) 색종이 개수를 저장할 리스트
result = [0, 0]

# 분할 정복 시작
divide_paper(0, 0, N, paper, result)

# 결과 출력
print(result[0])  # 흰색 색종이 개수
print(result[1])  # 파란색 색종이 개수

 

어렵다 😵

1. 문제 이해 및 분석

- 입력 / 처리 / 출력 

 

2. 알고리즘 설계

- 그 알고리즘이 필요한 이유 파악

- 필요한 함수들 구상

 

3. 작은 예제로 테스트

 

4. 코드 구조 설계

- 전체 구조 설계

- 메인 로직 설계

- 각 함수의 파라미터 결정

 

5. 단계별 구현

 

6. 테스트 및 디버깅

 

7. 최적화 고려

- 불필요한 반복문 제거

- 메모리 사용량 개선

- 재귀 깊이 고려