[백준 BOJ_2630] 색종이 만들기 Python 풀이

출처: 백준 온라인 저지

문제

풀이

우선 종이의 한변의 길이 n과 시작하는 좌표 (y, x)를 받는 quadtree함수를 만들어 주었습니다.

n이 1일때는 제일 작은 경우(기저사례) 이기 때문에 해당 좌표의 값을 포함한 list로 반환해줍니다.

문제에서 힌트를 얻을 수 있듯이 종이를 좌측상단, 우측상단, 좌측하단, 우측하단으로 4등분하여 더이상 자를 수 없을 때까지 재귀호출해주면 됩니다.

하지만 해당 부분이 같은 색으로 이루어져 있다면 더이상 쪼개지 않고 반환해주어야 하기 때문에 이중 for loop을 돌려 확인해주었습니다. 만약 모두 같은 색으로만 이루어져 있다면 역시 해당 좌표의 값을 포함한 list로 반환해줍니다.

n을 반으로 나누어 준 뒤, 4등분한 종이들의 시작좌표 또한 나눈 n값으로 아래의 그림과 같이 바꿔줍니다.

재귀호출한 네 부분들의 값을 하나의 list로 합해준 뒤 반환해줍니다. 반환된 list는 파란색 종이는 1로, 하얀색 종이는 0으로 나타내기 때문에 list의 sum값은 파란색 종이의 개수를 알려줍니다. list의 길이에서 파란색 종이 개수를 빼주면 하얀색 종이의 개수도 알 수 있게 됩니다.

코드

def quadtree(n, y, x):
    if n == 1: 
        return [paper[y][x]]
    check = True
    for i in range(y, y+n):
        if not check:
            break
        for j in range(x, x+n):
            if paper[y][x] != paper[i][j]:
                check = False
                break
    if check:
        return [paper[y][x]]
    new_n = n // 2
    ret = quadtree(new_n, y, x) + quadtree(new_n, y, x+new_n) + quadtree(new_n, y+new_n, x) + quadtree(new_n, y+new_n, x+new_n)
    return ret

C = int(input())
paper = [ list(map(int, input().split())) for _ in range(C)]
result = quadtree(C, 0, 0)
blue = sum(result)
print(len(result)-blue)
print(blue)