[Algorithm] 백준 BOJ 2630 색종이 만들기 python 파이썬 분할정복 실버2

Private 난이도 : ♥♥♡♡♡

2630번: 색종이 만들기

import sys
input=sys.stdin.readline

n=int(input().strip())
graph=list()
for i in range(n):
    graph.append(list(map(int,input().strip().split(' '))))

blue=0
white=0
direction=[[0,0,1,1],[0,1,0,1]]

def check(n,x,y):
    color=graph[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if graph[i][j]!=color:
                return False
    return True

def s(n,x,y):
    global blue
    global white
    if n==1:
        if graph[x][y]:
            blue+=1
        else:
            white+=1
    else:
        if check(n,x,y):
            if graph[x][y]:
                blue+=1
            else:
                white+=1
            return
        next_n=n//2
        for i in range(4):
            s(next_n,x+direction[0][i]*next_n,y+direction[1][i]*next_n)
s(n,0,0)

print(white)
print(blue)

백준 제출 버전

 

설명

• 현재 확인하려는 정사각형의 한 변의 길이와 그 사각형의 첫 번째 좌표(좌상단)을 함수에 넣고
  • 해당 정사각형이 1 이나 0 둘 중 하나로 이루어져 있다면 그 색으로 카운트
  • 다른 종이와 섞여있다면 변의 길이를 반으로 줄인 후 다시 탐색한다
• s(next_n,x+direction[0][i]*next_n,y+direction[1][i]*next_n)
  • 해당 함수를 부르는 부분이 가장 핵심인데
  • direction에 미리 1,2,3,4 분면의 좌상단을 계산할 수 있도록 했다.
• (함수 s 가 메인인데, 당시에 먼저 문제 풀기로 내기를 해서 아무렇게나 이름을 지어버렸습니다)

배운 점

•  UnboundLocalError
  • 함수 안의 global을 넣지 않으면 정의하지 않은 변수를 수정하기 때문에 에러가 난다.
  • 자세한 내용은 이 블로그를 참고하자