[python/백준/분할정복] 1780: 종이의 개수

문제

풀이

• 종이를 9x9 => 3x3 => 1x1로 줄여가며 색상을 확인한다.

	1. 종이 9*9를 탐색한다.
    2-1. 만약 종이의 시작 부분과 탐색 부분이 다르다면 => 종이 크기를 1/3로 줄인다. 
    	 
         종이를 같은 크기의 종이 9개로 자르므로(3*3), 
         9개에 대해서 따로 색상을 확인한다. (2-1번과 2-2를 반복)
         
    2-2. 종이의 시작 부분과 탐색부분이 같다면 => 종이의 종류를 세어준다. (+1)

코드

import sys

# 1. 입력받기 
n = int(input())
paper = []
for i in range(n):
    paper.append(list(map(int,sys.stdin.readline().split())))

# 종이 종류 RESULT 
result = {-1:0, 0:0,1:0}

# 2. 종이의 종류(-1, 0, 1)와 다르면 분할 
def divided(row,col,n):
    curr = paper[row][col] # 종이의 시작 

    for i in range(row, row+n):
        for j in range(col, col+n):
            # 현재 종이 종류와 다르다면 
            if paper[i][j] != curr:
                # 종이 1/3로 분할 (ex. n == 9 , n = 9 -> 3 -> 1 )
                next = n//3
                # 종이를 같은 크기의 종이 9개로 자르므로 
                divided(row, col, next) # 1번째 block (0,0)
                divided(row, col+next, next) # 2번째 block (0,1)
                divided(row, col+(next*2), next) # 3번째 block (0,2)
                divided(row+next, col, next) # 4번째 block (1,0)
                divided(row+next, col+next, next) # 5번째 block (1,1)
                divided(row+next, col+(next*2), next) # 6번째 block (1,2)
                divided(row+(next*2), col, next) # 7번째 block (1,0)
                divided(row+(next*2), col+next, next) # 8번째 block (1,1)
                divided(row+(next*2), col+(next*2), next) # 9번째 block (1,2)
                return 

    # 3. 종이 종류에 따라 count 
    result[curr] +=1 
    return 


divided(0,0,n)

# 4. 결과 return 
for i in result.values():
    print(i)

후기

분할정복 개념을 잘 몰라서 어려웠다ㅠㅠ
https://velog.io/@uoayop/BOJ-1780-%EC%A2%85%EC%9D%B4%EC%9D%98-%EA%B0%9C%EC%88%98Python 이분의 풀이를 보고 이해했다!
개념을 이해하니 조금 쉬웠다
다시 한번 풀어봐야겠다