백준 2630 - 색종이 만들기

 

처음 든 생각

- 정사각형이 성립하는지 안하는지 판단한 다음

- 정사각형이 만들어지지 않는다면 다시 4개로 쪼개서 확인한다.

- 크기가 1인 정사각형일 때가 재귀 탈출 조건일 것이다.

 

나의 답

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

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

blue = 0
white = 0

# 사각형 별 시작 좌표 + 크기 를 받아서
def search(sr, sc, n):
    global blue, white
    # 1의 갯수를 센다
    blue_count = 0
    for i in range(sr,sr + n):
        for j in range(sc,sc+n):
            if arr[i][j] == 1:
                blue_count += 1
    # 모두 1이면 파란 정사각형 성립            
    if blue_count == n**2:
        blue += 1
        return
    # 모두 0이면 하얀 정사각형 성립
    elif blue_count == 0:
        white += 1
        return
    # 정사각형이 만들어지지 않았다면 네개로 나눠서 다시 검색
    else:
        search(sr,sc,n//2)
        search(sr+n//2,sc,n//2)
        search(sr,sc+n//2,n//2)
        search(sr+n//2,sc+n//2,n//2)

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

 

정사각형이 성립하는지를 먼저 판단한다. 그러기 위해서 1의 개수를 세는 방법으로 확인하기로 했다. 1의 개수가 N^2 개라면 모두 1이라는 뜻이므로 파란색 정사각형이 만들어진 것이다. 만약 0개라면 하얀색 정사각형이 만들어진 것이다. 그러면 더이상 쪼개서 검색할 필요가 없으므로 리턴함으로써 함수를 종료한다.

 

만약 정사각형이 만들어지지 않았다면 다시 4개로 나눠서 검색한다. search 함수는 탐색할 정사각형의 가장 좌측 상단의 좌표를 매개변수로 받는다. 시작 좌표 값을 기준으로 4개로 나누는 것은 위의 코드대로 n//2 를 추가해주는 방식으로 조절하면 된다. 

---

사실 아이디어는 그렇게 어렵지 않게 떠올랐으나 구현에서 꽤나 애를 먹었다. 아직 재귀에 대한 그림이 머릿 속에서 빠릿빠릿하게 그려지지 않는 것 같다. 리턴하는 순서도 아직 하나하나씩 써가면서 확인하고 있어서 재귀에 대한 문제풀이가 좀 많이 필요할 것 같다.