코드
import sys
input = sys.stdin.readline
N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
res = []
def div(x, y, N):
fst = paper[x][y]
for i in range(x, x+N):
for j in range(y, y+N):
if fst != paper[i][j]:
div(x, y, N//2)
div(x, y + N//2, N//2)
div(x + N//2, y, N//2)
div(x + N//2, y + N//2, N//2)
return
if fst == 0:
res.append(0)
else:
res.append(1)
div(0, 0, N)
print(res.count(0))
print(res.count(1))- paper를 초기화하는 동시에 값을 저장할 수 있다니! 구글링을 통해 알게 되었다. 매우 간편한 것 같다. 앞으로 저렇게 써야징
- 나누어진 색종이들을 모두 돌면서 첫 색깔과 달라지는 순간 4등분으로 나눈다. 또다시 나누어진 색종이도 모두 색깔이 같아야 하므로 재귀를 호출해서 같아지는 순간까지 계속 나눈다.
- 여기서 중요한 점! return을 반드시 써야 한다. 모든 같은 색의 색종이를 가질 때까지 4번의 재귀를 호출하는 건데, return은 다 했으면 이제 원래의 위치로 돌아가! 라는 역할을 한다. 그래서 return을 안 쓰면 밑의 if문까지 다 시행돼서 0과 1이 어마어마하게 추가될 것이다..
- if문으로 넘어갔다는 것은 모든 색종이의 색이 같다는 것이다. 그래서 해당 색종이의 색을 res리스트에 넣어준다.
- 흰색과 검정색 색종이들의 개수를 res리스트를 통해 각각 출력하면 끝!
결과
재귀함수는 너무 어렵다.. 더더 연습해야지
