[ BOJ / 파이썬 ] 2630 색종이 자르기 + 도형 자르고 그리는 재귀 문제 공략

|  제출 1  |

 

import sys
input = sys.stdin.readline

n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]

paper_color = { 0: 0, 1: 0}

def check_paper(x, y, n):

  if n == 1:
    paper_color[paper[x][y]] += 1
    return

  isSame = True
  for i in range(n):
    if not isSame:
      break    
    for j in range(n):
      if paper[x][y] != paper[x+i][y+j]:
        isSame = False
        break

  if isSame:
    paper_color[paper[x][y]] += 1
  else:
    check_paper(x, y, n//2)
    check_paper(x, y+n//2, n//2)
    check_paper(x+n//2, y, n//2)
    check_paper(x+n//2, y+n//2, n//2)

check_paper(0, 0, n)

for color in paper_color.values():
  print(color)

 

이제는 조금 익숙해진 사각형 자르기 문제였다.

그런데도 check_paper 부분에서 새 x, y값을 받아온 x, y값이 아니라 0, 0 기준으로 해서 제대로 종이가 잘려 들어가지 않는 실수를 했다. 해당 문제의 알고리즘적인 것이 이해가 되니까 디버깅이 빠르게 됐다.

 

 

---

 

 

재귀 문제 중 자르고 반복하는 도형 문제는 어느정도 동일 방법으로 귀결되는 것 같다. 

 

1. 동일 함수를 재귀적으로 반복해서 호출한다.

 

2. 이 때 호출함수에 들어가는 파라미터는

 

    2-1. 전체 길이를 늘였거나, 줄어들게 설정해서 넣는다. (그래서 인풋값이 2배수 3배수 등으로 들어온다.)

    2-3. 해당 도형의 시작 포인트를 리뉴얼해서 넣어준다.

           2-1과 같은 범위로 조작된다 보통. 이번 시작 범위에서 더해지거나 빼지는 방식

 

3. 함수 내에서 재귀를 끝낼 초기값을 설정한다. 이건 문제에 따라서 길이가 1일수도, 3,5,...일수도 도형에 따라서 지정한다.

 

ㅡ

이 때 주의할 것은

 

1) 찾는 도형의 개수를 셀 때는,

    외부 배열을 지정해주고 그걸 업데이트해주면 되는데,

 

2) 만약 도형을 출력하는 문제라면, 곧이 곧대로 출력하기보다는

    최종 도형이 나올 배열을 함수 호출 전 미리 선언하고 그걸 업데이트시켜나가준다.

    그리고 마지막에 join메서드를 이용해서 한 번에 쭉 뽑아준다.