2630. 색종이 만들기

문제

백준 2630번 색종이 만들기

---

풀이

분할정복 알고리즘 너무 오랜만이라서 풀이 방법 완전히 까먹고있었다...

병합정렬 알고리즘 보면서 개념 다시 익히고,,
상태트리 그려본 다음에야 코드를 어떻게 짤지 생각해냈다.

재귀탐색을 통해 하얀 색종이와 파란 색종이가 모두 몇 장인지 계산한다.

같은 색이 아닐 경우 색종이가 네개로 나눠지기 때문에 상태트리 역시 가지를 4개씩 뻗어나간다.

f(size, x, y)에서 size는 해당 구역의 크기, x, y는 해당 구역의 시작 인덱스이다.

size 가 1이 되면 해당 구역의 색깔이 무엇인지 리턴한다.

네 구역의 리턴값을 리스트 area에 저장하고,
모두 같은 값이면 -> 해당 구역의 색깔을 리턴
같은 값이 아니면 -> 흰색과 파란색의 개수를 더함

탐색을 모두 마치고 메인함수에서 호출한 f(n, 0, 0)이 종료되면 마지막 값 last_val의 결과에 따라 1이면 blue에, 0이면 white에 1을 더해준다.

import sys

def f(size, x, y):
    global white, blue
    if size == 1: return board[x][y]
    else:
        nxt_n = size // 2
        area = [0, 0, 0, 0]
        area[0] = f(nxt_n, x, y)
        area[1] = f(nxt_n, x, y + nxt_n)
        area[2] = f(nxt_n, x + nxt_n, y)
        area[3] = f(nxt_n, x + nxt_n, y + nxt_n)
        if all(x == 1 for x in area) or all(x == 0 for x in area): return area[0]
        else:
            white += area.count(0)
            blue += area.count(1)
            return -1

n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
white, blue = 0, 0
last_val = f(n, 0, 0)
if last_val == 1: blue += 1
elif last_val == 0: white += 1
print(f'{white}\n{blue}')