백준 2630 색종이 만들기(파이썬)

재귀함수식으로 색이 다를때마다 4등분 하는 것이지만, 영역마다 잘라진 종이의 색을 count하는 것이 어렵다.

n=int(input())
paper = [list(map(int, input().split())) for i in range(n)] #리스트 생성
result=[]

def cut(x,y,n):
  color=paper[x][y] # 색 저장
  for i in range(x,x+n):
    for j in range(y, y+n):
      if color!=paper[i][j]: # 4등분
        cut(x,y,n//2)
        cut(x,y+n//2,n//2)
        cut(x+n//2, y, n//2)
        cut(x+n//2, y+n//2, n//2) #호출 시 항상 사분면의 왼쪽위 좌표로 호출
        return

  if color!=0: # 종이가 한 장이거나 잘라진 종이색이 모두 같으면 count
    result.append(0)
  else:
    result.append(1)


cut(0,0,n)
print(result.count(1)) #파랑
print(result.count(0)) #흰색

아이디어

핵심은 2차원 배열속에서 2중 for문으로 영역내에서 값이 같은지 조사하고 다르면 4등분하고, 같으면 하얀색과 파란색을 count하는점이다.

 

이게 가능한 것은 return시에 n//2로 크기를 보내기 때문이다.