[BOJ][Python]2630번 풀이

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

import sys
ssr = sys.stdin.readline

def sol(r,c,length):
    global paper_cnt, blue_cnt
    std = 0
    color_cnt = 0
    for i in range(r,r+length):
        for j in range(c,c+length):
            std += 1
            color_cnt += b[i][j]
    if std == color_cnt or color_cnt == 0:
        paper_cnt += 1
        blue_cnt += color_cnt//std
        return
    else:
        #if length > 1:
        length //= 2
        sol(r,c,length)
        sol(r,c+length,length)
        sol(r+length,c,length)
        sol(r+length,c+length,length)

n = int(ssr())
b = [list(map(int, ssr().split())) for _ in range(n)]
paper_cnt = 0
blue_cnt = 0
sol(0,0,n)
print(paper_cnt-blue_cnt)
print(blue_cnt)

오랜만에 재밌는 문제였습니다. 처음엔 어떻게 할지 좀 막막하다 싶었는데 손으로 조금씩 과정을 체크해보니까 어떻게 풀면 좋을지 감이 좀 잡히더라구요. 지금 보니까 몇 개 빼도 될만한 과정들이 보이긴 합니다(std 변수는 굳이 필요없을 것 같다든가).

 

제가 접근한 방법에 대해서 설명을 드리자면 일단 재귀로 풀어야 하는 것이 명백했기 때문에 어떻게 하면 재귀적으로 깔끔하게 짤 수 있을까를 고민하면서 어떻게 종이 숫자를 셀지에 대해서 고민을 좀 했습니다. 그러다가 모든 좌표를 하나씩 돌면서 값을 체크한 다음에 해당 영역이 한 가지 색으로 이뤄져있지 않을 경우에 영역의 갯수와 좌표값에서 차이가 나겠구나 생각을 해서 반복문이 돌 때 마다 std 변수는 1씩 증가 시키고 color_cnt는 해당 좌표값으로 증가 시켰습니다. 좌표값이 0이라면 std는 1이 오르지만 color_cnt는 증가하지 않으니 해당 영역이 한가지 색으로만 이루어져 있지 않다는 뜻이 되기 때문입니다. 따라서 해당 방법을 이용해 한가지 색으로만 이루어져있을 때와 아닐 때를 구분해서 조건문을 작성하고 한가지 일 때는 종이의 갯수를 1 올리고 파란색 종이의 값을 color_cnt // std 만큼 증가 시킵니다. 만약 해당 영역이 전부 파란색일 경우 color_cnt // std 는 1이 나올 것이고 전부 흰색이라면 0이 나오기 때문입니다(0만큼 증가시킨다는 것은 증가하지 않는다는 것과 같기 때문). 한가지 색이 아닐 경우에는 문제에서 주어진 방법대로 4등분해서 다시 탐색해야 하므로 재귀 호출을 이용해주면 됩니다.

 

위에서도 말했지만 정말 오랜만에 즐거웠습니다. 최근에 크게 즐거운 일들이 별로 없었던 것 같은데 얼마만에 뿌듯한 웃음을 멈출 수 없었는지 모르겠네요.