[백준 2630번] 색종이 만들기 - python

문제 링크

https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

풀이

- 분할 정복 문제 

:  주어진 문제를 작은 문제로 분할하여 문제를 해결하는 방법으로, 재귀적으로 자기 자신을 호출하여 그 연산 단위를 줄여나가는 알고리즘이다. 

- 평소 문제를 풀 때 재귀를 잘 사용하지 않고 분할 정복 문제를 처음 접해봐서 문제 해결 방법을 떠올리는게 쉽지 않았다. 

- graph를 순회하면서 처음 시작한 graph[i][j]의 값과 달라지는 경우 범위를 4등분하여 재귀적으로 호출한다.

이 때 4등분하는 방식은 n을 2등분하고, 첫 시작점 좌표 값을  4등분 했을 때 각각의 첫 시작점 좌표로 설정해준다. 

sol(x, y, n//2)
sol(x + n//2, y , n//2)
sol(x, y + n//2 , n//2)
sol(x + n//2, y + n//2, n//2)

- 처음 시작한 graph[i][j]의 값이 0일 때는 하얀색종이의 개수 +1 

- 처음 시작한 graph[i][j]의 값이 1일 때는 파란색종이의 개수 + 1

# 분할 정복

# 흰색 색종이 개수
count0 = 0
# 파란 색종이 개수 
count1 = 0

def sol(x, y, n):
  global count0
  global count1
  
  color = graph[x][y]
  
  for i in range(x, x+n):
    for j in range(y, y+n):
      # 처음 시작한 색과 다르면 
      if color != graph[i][j]:
        # 4등분하여 재귀적으로 호출 
        sol(x, y, n//2)
        sol(x+n//2 , y , n//2)
        sol(x, y +n//2 , n//2)
        sol(x+n//2, y+n//2, n//2)
        return
  # 흰색 색종이 개수 + 1 
  if color == 0:
    count0 += 1 
  # 파란 색종이 개수 + 1
  else:
    count1 += 1 
    
n = int(input())

graph = []

for _ in range(n):
  graph.append(list(map(int,input().split())))

sol(0,0,n)
print(count0)
print(count1)