Note
분할 정복(Divide and Conquer) 알고리즘을 활용하여 2D 그리드를 재귀적으로 분할하여 해결하는 문제입니다.
문제
아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.
전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.
전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.
문제 링크: https://www.acmicpc.net/problem/2630
입력
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 잘라진 하얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.
예제
예제 입력 1:
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
예제 출력 1:
9
7
문제 분석
이 문제는 분할 정복 알고리즘을 사용하는 전형적인 문제입니다.
핵심 포인트
- 분할: 전체 종이가 같은 색이 아니면 4등분
- 정복: 각 부분을 재귀적으로 처리
- 결합: 하얀색과 파란색 색종이의 개수를 합침
- 기저 조건: 모든 칸이 같은 색이거나 크기가 1×1일 때
해결 방법
분할 정복 알고리즘을 사용합니다:
- 현재 영역이 모두 같은 색인지 확인
- 같으면 해당 색의 색종이 1장 추가
- 다르면 4등분하여 각각 재귀적으로 처리
- 결과를 합침
코드 구현
제공된 코드
import sys
readline = sys.stdin.readline
n = int(readline())
grid: list[list[int]] = []
for _ in range(n):
row = list(map(int, readline().split()))
grid.append(row)
# 색종이 몇장인지 검사하는 것
def count_paper(y, x, side) -> tuple[int, int]:
# 좌상단 칸 * (side * side) == 배열의 합일 경우 : 1장이다.
sum = 0
for i in range(side):
for j in range(side):
sum += grid[y + i][x + j]
is_one = grid[y][x] * (side * side) == sum
if is_one:
if grid[y][x] == 0:
return (1, 0)
return (0, 1)
# 4사분면으로 나눠서 더한다.
half = int(side / 2)
q1 = count_paper(y, x + half, half)
q2 = count_paper(y, x, half)
q3 = count_paper(y + half, x, half)
q4 = count_paper(y + half, x + half, half)
return (q1[0] + q2[0] + q3[0] + q4[0],
q1[1] + q2[1] + q3[1] + q4[1])
result = count_paper(0, 0, n)
print(result[0])
print(result[1])코드 분석
1. 입력 처리
import sys
readline = sys.stdin.readline
n = int(readline())
grid: list[list[int]] = []
for _ in range(n):
row = list(map(int, readline().split()))
grid.append(row)- 입력 최적화를 위해
sys.stdin.readline()사용 - N×N 크기의 그리드를 입력받음
2. 분할 정복 함수
def count_paper(y, x, side) -> tuple[int, int]:
# 현재 영역의 합 계산
sum = 0
for i in range(side):
for j in range(side):
sum += grid[y + i][x + j]
# 모두 같은 색인지 확인
is_one = grid[y][x] * (side * side) == sum동일 색 확인 방법:
- 좌상단 칸의 값 × 영역 크기 = 영역의 합
- 이 조건이 참이면 모든 칸이 같은 색
3. 기저 조건
if is_one:
if grid[y][x] == 0:
return (1, 0) # 하얀색 1장
return (0, 1) # 파란색 1장- 모든 칸이 같은 색이면 해당 색의 색종이 1장 반환
- 반환값:
(하얀색 개수, 파란색 개수)
4. 분할 및 재귀 호출
# 4사분면으로 나눠서 더한다.
half = int(side / 2)
q1 = count_paper(y, x + half, half) # 우상단
q2 = count_paper(y, x, half) # 좌상단
q3 = count_paper(y + half, x, half) # 좌하단
q4 = count_paper(y + half, x + half, half) # 우하단
return (q1[0] + q2[0] + q3[0] + q4[0],
q1[1] + q2[1] + q3[1] + q4[1])4등분:
half = side // 2- Q1 (우상단):
(y, x + half, half) - Q2 (좌상단):
(y, x, half) - Q3 (좌하단):
(y + half, x, half) - Q4 (우하단):
(y + half, x + half, half)
개선된 코드
더 명확하고 효율적으로 작성한다면:
import sys
readline = sys.stdin.readline
def count_paper(grid, y, x, size):
# 현재 영역이 모두 같은 색인지 확인
first_color = grid[y][x]
is_uniform = True
for i in range(y, y + size):
for j in range(x, x + size):
if grid[i][j] != first_color:
is_uniform = False
break
if not is_uniform:
break
# 기저 조건: 모두 같은 색
if is_uniform:
if first_color == 0:
return (1, 0) # 하얀색
else:
return (0, 1) # 파란색
# 분할: 4등분
half = size // 2
# 정복: 4개의 사분면을 재귀적으로 처리
q1 = count_paper(grid, y, x + half, half) # 우상단
q2 = count_paper(grid, y, x, half) # 좌상단
q3 = count_paper(grid, y + half, x, half) # 좌하단
q4 = count_paper(grid, y + half, x + half, half) # 우하단
# 결합: 결과를 합침
white = q1[0] + q2[0] + q3[0] + q4[0]
blue = q1[1] + q2[1] + q3[1] + q4[1]
return (white, blue)
# 메인 코드
n = int(readline())
grid = [list(map(int, readline().split())) for _ in range(n)]
white, blue = count_paper(grid, 0, 0, n)
print(white)
print(blue)개선 사항:
- 동일 색 확인 로직을 더 명확하게
- 변수명을 더 명확하게 (
side→size) - 함수에 grid를 파라미터로 전달
시간 및 공간 복잡도
시간 복잡도
- 동일 색 확인: O(size²) - 각 영역의 모든 칸 확인
- 재귀 호출: 최대 O(log n) 레벨
- 전체: O(n² log n) - 최악의 경우
최적화 가능: 동일 색 확인을 더 효율적으로 할 수 있지만, 이 문제에서는 충분히 빠릅니다.
공간 복잡도
- 그리드 저장: O(n²)
- 재귀 호출 스택: O(log n)
- 전체: O(n²)
예제 동작 과정
예제 입력 1: n=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
분할 정복 과정:
- 전체 8×8 확인 → 다른 색 섞임 → 4등분
- 각 4×4 영역을 재귀적으로 처리
- 더 작은 영역들도 필요시 계속 분할
- 최종적으로 하얀색 9장, 파란색 7장
주의사항
1. 좌표 순서
그리드에서 grid[y][x] 형태로 접근:
- y: 행 (세로)
- x: 열 (가로)
2. 사분면 분할
4등분할 때 좌표 계산:
- Q1 (우상단):
(y, x + half, half) - Q2 (좌상단):
(y, x, half) - Q3 (좌하단):
(y + half, x, half) - Q4 (우하단):
(y + half, x + half, half)
3. 기저 조건
크기가 1×1이 되면 자동으로 기저 조건에 도달합니다 (모든 칸이 같은 색).
관련 알고리즘
- 분할 정복 (Divide and Conquer)
- Python 입력 최적화
- 재귀 (Recursion)