[백준 2630번] 색종이 만들기 - 파이썬

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

2630번: 색종이 만들기

 

💡문제 분석 요약

아래와 같이 정사각형 모양으로 나누어 진 종이가 있을 때, 파란색 종이의 개수와 흰색 종이의 개수를 구하여라.

 

💡알고리즘 설계

현재 칸의 종이 색과 첫번째 칸의 종이의 색이 다르면 현재 종이를 4등분으로 자르고, 다시 탐색한다.

현재 종이에 있는 모든 칸이 색깔이 같다면, 그 색의 count를 하나 더한다.

1. 종이의 색 정보를 입력받는다

2. cut 함수를 호출한다.

3. cut 함수에서, 해당 종이의 모든 칸을 이중 for문을 이용해 검사하고, 첫번째 칸 (color=arr[y][x])과 다를 경우 종이의 범위를 4등분으로 나눠, 나눠진 종이마다 cut 함수를 새로 호출한다. 그 후 return으로 그 함수는 탐색을 종료한다.

4. 만약 함수가 return되지 않았을 경우, 그 종이의 모든 칸이 첫번째 칸의 색과 같다는 의미이므로, 색에 따라 white개수나 blue 개수를 더한다.

5. 모든 함수 호출이 끝난 후, 흰색 종이의 개수와 파란색 종이의 개수를 출력한다.

 

 

💡코드

import sys
input = sys.stdin.readline

N=int(input())
arr=[]
for _ in range(N):
    row=list(map(int, input().split()))
    arr.append(row)

white, blue = 0, 0

def cut(x, y, N):
    global white, blue
    color=arr[y][x]

    for i in range(y,y+N):
        for j in range(x, x+N):
            if color != arr[i][j]:
                cut(x, y, N//2)        # 2사분면
                cut(x, y + N//2, N//2)      # 3사분면
                cut(x + N//2, y, N//2)      # 1사분면
                cut(x + N//2, y + N//2, N//2)    # 4사분면
                return
        
    if color==0:
        white+=1
    else:
        blue+=1

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

 

💡 느낀점 or 기억할 정보

재귀를 어떤 방식으로 활용할 수 있을지가 중요할 것 같다.