1answer = [0, 0]
2
3def solution(arr):
4 def recursion(sx, sy, k):
5 global answer
6 origin = arr[sy][sx]
7 cnt = 0
8 for i in range(sx, sx+k):
9 for j in range(sy, sy+k):
10 if origin != arr[j][i]:
11 recursion(sx, sy, k//2)
12 recursion(sx+k//2, sy, k//2)
13 recursion(sx, sy+k//2, k//2)
14 recursion(sx+k//2, sy+k//2, k//2)
15 return
16 answer[origin] += 1
17
18 recursion(0, 0, len(arr))
19 return answer
๋ฌธ์
- 0๊ณผ 1๋ก ์ด๋ฃจ์ด์ง 2^n x 2^n ํฌ๊ธฐ์ 2์ฐจ์ ์ ์ ๋ฐฐ์ด arr์ ์์ถํ๋ ค ํ๋ค
- ์์ถํ๋ ๋ฐฉ๋ฒ์
- ๋น์ ์ด ์์ถํ๊ณ ์ ํ๋ ํน์ ์์ญ์ S๋ผ๊ณ ์ ์ํ๋ค
- ๋ง์ฝ S ๋ด๋ถ์ ์๋ ๋ชจ๋ ์๊ฐ ๊ฐ์ ๊ฐ์ด๋ผ๋ฉด, S๋ฅผ ํด๋น ์ ํ๋๋ก ์์ถ์ํจ๋ค
- ๊ทธ๋ ์ง ์๋ค๋ฉด, S๋ฅผ ์ ํํ 4๊ฐ์ ๊ท ์ผํ ์ ์ฌ๊ฐํ ์์ญ์ผ๋ก ์ชผ๊ฐ ๋ค, ๊ฐ ์ ์ฌ๊ฐํ ์์ญ์ ๋ํด ๊ฐ์ ๋ฐฉ์์ ์์ถ์ ์๋ํ๋ค
- TC
- input
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]