** 알고리즘 오답노트 17 (백준 - 2630)

색종이 만들기

분할 정복, 재귀 함수를 이용하여 푸는 문제
색종이 한 섹션 안에 있는 모든 요소가 같지 않으면 4분할 해서 스스로를 다시 호출함.
이때 갈라진 4개의 함수에 매개변수를 어떻게 넣어야할지 잘 생각해야함!
색종이 한 섹션 안에 있는 모든 요소가 같아지면 바로 return 해주면 되므로 탈출조건은 따로 필요없음.

• 틀린 부분 : 4분할로 나눠진 매개변수 부분을 잘못 생각함;; blue, white 변수는 함수 외부에 선언해야한다는걸 생각 못함;;

import sys
num = int(sys.stdin.readline())
paper = []
for _ in range(num):
  paper.append(list(map(int, sys.stdin.readline().split())))
 
blue = 0
white = 0
def cut_paper(width_start, width_finish, height_start, height_finish):
  global blue, white
  # 함수 내에 blue, white 변수를 넣으면 재귀적으로 호출될때마다 0으로 초기화 되므로 함수 밖에서 선언되어야 하는데,
  # 함수 밖에 있는 변수를 변경해서 위해 global로 선언해줘야 함.
  # 그냥 값을 가져오기만 한다면 global 선언 안해도 됨.
  first = paper[height_start][width_start]
  for i in range(height_start, height_finish+1):
    for j in range(width_start, width_finish+1):
      if first != paper[i][j]:
      # 섹션 안에 하나라도 색이 다른 부분이 있다면 바로 잘라버리면 됨.
        cut_paper(width_start,(width_start+width_finish)//2,height_start,(height_start+height_finish)//2)
        cut_paper((width_start+width_finish)//2+1,width_finish,height_start,(height_start+height_finish)//2)
        cut_paper(width_start,(width_start+width_finish)//2,(height_start+height_finish)//2+1,height_finish)
        cut_paper((width_start+width_finish)//2+1,width_finish,(height_start+height_finish)//2+1,height_finish)
        return
  if first == 1:
    blue += 1
  else:
    white += 1
  return # 함수의 마지막엔 끝을 의미하는 return만 써주고 함수 외부에 선언된 blue, white 값만 프린트 해주면 답을 구할수 있음.
    
cut_paper(0,num-1,0,num-1)
print(white)
print(blue)

• github commit
• 문제 링크