백준 2630 문제(파이썬)

색종이 만들기

풀이 과정

1. 전체 범위부터 값이 한 가지 값으로만 이루어져 있는지 확인(check)

2. 4등분하여 각 등분한 부분마다 한 가지 값으로 이루어져 있는지 확인(재귀)

3. 확인이 된 부분은 어떤값으로(0 or 1) 이루어져 있는지 확인하고 값에 따라 white, blue 값 카운트 업

4. 확인이 안된부분은 또 한 번 4등분

 

---

 

 

from sys import stdin
N = int(stdin.readline())

paper = [list(map(int, stdin.readline().split())) for _ in range(N)]

white = 0 # 값이 0이면 흰색 카운트 업
blue = 0  # 값이 1이면 파란색 카운트 업

def check(x, y, N):
    compare_color = paper[x][y]    # 비교할 기준 색깔을 정한다.
    for i in range(x, x + N):
        for j in range(y, y + N):
            if paper[i][j] != compare_color:
                return False
    return True

def solve(x, y, N):
    global white, blue

    if check(x, y, N):
        if paper[x][y] == 0:
            white += 1
        else:
            blue += 1
        return
    else:
        N //= 2
        solve(x, y, N)
        solve(x, y+N, N)
        solve(x+N, y, N)
        solve(x+N, y+N, N)
        return

solve(0, 0, N)
print(white)
print(blue)

 

 

함수를 2개 사용하는 방식을 가져왔고 각 함수는

 

1. 값이 하나로 일치하는지 체크하는 역할  def check(x, y, N)

2. 체크해서 아니면 쪼개면서 white, blue 박스가 몇 개인지 검증하는 역할 def solve(x, y, N)

 

로 구분해서 풀었다.

 

함수안에 함수가 들어가게 되지만 함수의 사용 목적만 잘 기억하고 보면 잘 이해된다.

 

---

 

 

check 함수

 

 

        범위를 각각 range(x, x + N) , range(y, y + N)으로 설정한 이유는 네모 전체를 봐야 하기 때문이다.(변의길이 N)

 

 

---

 

solve 함수

가장 먼저 쪼개기 전에 색이 한 가지로 통일되는지 확인 작업(check함수)이 시작되고 

False이면  4등분 하고 각 분할 별로 재귀 함수를 만족할 때까지 돌린다. 

(해당 분할안에 몇 개의 white or blue 박스가 존재하는지 확인할때까지 깊이 들어가면서 계속 쪼개 줌)