색종이 만들기
분할 정복, 재귀 함수를 이용하여 푸는 문제
색종이 한 섹션 안에 있는 모든 요소가 같지 않으면 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)
빠굥