📑문제
0 또는 1의 값을 가지는 2차원 배열에서 정사각형 형태의 0,1을 찾자
전체 배열에 값이 동일하지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 각각에 대해서도 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.
💡 핵심
재귀함수를 이용하여 분할정복
해당 문제를 풀기에 가장 적합한 방법인 재귀함수를 이용하여 문제 풀이를 진행하였다. 배열 입력을 받은 후 해당 배열을 재귀함수쪽으로 넘겨주고 해당 재귀함수에서는 배열에 있는 값 중 어떤 값을 선택하고 그 선택한 값과 하나라도 다른 숫자가 있다면 분할 진행한다. 분할을 진행할 때에 4등분으로 진행함으로 함수도 4개를 다른 x,y를 주며 다시 재귀한다.
division_conqu(x,y,n//2)
division_conqu(x,y + n//2,n//2)
division_conqu(x+ n//2,y,n//2)
division_conqu(x+ n//2,y + n//2,n//2)첫 번째 재귀의 경우
# divsion_conqu(0,0,4)
# divsion_conqu(0,0,2)
#--------------------------
# divsion_conqu(0,0,1) => blue
# divsion_conqu(0,1,1) => wh
# divsion_conqu(1,0,1) => wh
# divsion_conqu(1,1,1) => wh이러한 형식으로 blue, white를 찾아낼 수 있을 것이고, 이 후에는
divsion_conqu(0,4,4)를 진행할 것이다.
❗ 어려웠던, 곤란했던
1. 재귀함수 말고 다른 방법은..?
문제 풀이를 어떻게 접근해야할지 조금 난감했다. 해당 문제에 대해서 어떻게 접근해야할지 생각할수록 재귀함수를 사용해서 풀어냄이 바람직하게 생각이 되었는데, 학교 수업을 수강하면서 자주 들은 이야기로는 재귀함수 사용을 권장하지 않는다 들었기에 재귀함수를 제하고 다른 방법으로 풀려고 하였다. 그러나 많은 생각을 하였으나, 재귀함수로 푸는 방법 밖에 생각이 나지 않아 결국 재귀함수를 이용하여 풀기로 하였다.
2. 재귀함수를 어떻게 하더라
앞서서 말하였듯이 재귀함수 자체를 사용하지 않는 것이 좋다고 학습하여서 흐름이나 사용방법 자체가 너무 오랜만이라서 어떻게 해야할지 감이 오지 않았다. 그래서 먼저 간단한 재귀함수를 먼저 공부하기로 마음먹고 서칭을 하면서 간단한 재귀함수에 대해서 공부를 하였다.
def factorial(n):
if(n > 1):
return (n * factorial(n - 1))
else:
return 1
factorial(5)🧾 전체 코드
import sys
input=sys.stdin.readline
num = int(input())
ary = [[int(x) for x in input().split()] for y in range(num)]
blue = 0
white = 0
def division_conqu(x, y, n):
base_color = ary[x][y]
global blue
global white
for i in range(x, x+n):
for j in range(y, y+n):
if(ary[i][j] != base_color):
division_conqu(x,y,n//2)
division_conqu(x,y + n//2,n//2)
division_conqu(x+ n//2,y,n//2)
division_conqu(x+ n//2,y + n//2,n//2)
return 1
if base_color == 0:
white = white + 1
else:
blue = blue + 1
division_conqu(0,0, num)
print(white)
print(blue)
