[알고리즘] 백준 2630 색종이 만들기 - S2

2024.10.10 풀이

import sys
input=sys.stdin.readline

n=int(input())
arr=[]
for _ in range(n):
    arr.append(list(map(int, input().split())))

blue, white=0,0
def search(a,b,c,d):
    global blue, white
    if b-a<1 or d-c<1:
        return
    cnt=0
    k=arr[a:b]
    for i in k:
        cnt+=sum(i[c:d])
    if cnt==0:
        white+=1
        return
    elif cnt==(b-a)*(d-c):
        blue+=1
        return

    search(a, a+(b-a)//2, c, c+(d-c)//2) #1
    search(a, a+(b-a)//2, c+(d-c)//2, d) #2
    search(a+(b-a)//2, b, c, c+(d-c)//2) #3
    search(a+(b-a)//2, b, c+(d-c)//2, d) #4

search(0,n,0,n)
print(white, blue, sep="\n")

---

다른 풀이

import sys

N = int(sys.stdin.readline())
square = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
white = 0
blue = 0

def cut(row, column, n):
    global white, blue
    color = square[row][column]
    for i in range(row, row + n):
        for j in range(column, column + n):
            if color != square[i][j]:
                cut(row, column, n // 2)  # 1사분면
                cut(row, column + n // 2, n // 2)  # 2사분면
                cut(row + n // 2, column, n // 2)  # 3사분면
                cut(row + n // 2, column + n // 2, n // 2)  # 4사분면
                return
    if color == 0:
        white += 1
    else:
        blue += 1
cut(0, 0, N)
print(white)
print(blue)

---

check point

• 분할정복
  - row, column: 현재 영역의 시작 좌표, n: 현재 탐색하려는 영역의 크기
  • 시작지점(row, column)과 n*n의 영역이
    • 모두 같은 색이라면 -> 시작지점의 색 +1
    • 색이 다른게 있다면 4등분하여 더 작은 영역으로 나누어 탐색 -> 시작지점과 영역의 크기로 쪼개기