[항해99]알고리즘_07

[Python] 백준 2630 색종이 만들기

   문제분석   

# 분할정복(Divide and Conquer)

  - 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법

  - 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄여가는 방식

# 한변의 길이 n을 입력값을 받고

# 변수를 하나 선언해서 두번째 입력값(각 색종이들의 숫자)을 리스트 형식으로 받는다.(이중리스트)

# 각 종이를 확인하여 0이나 1만 가지고 있는 색종이 발견시 추가할 리스트(result)를 초기화 한다.

# 재귀함수를 이용해 반복문을 돌면서 시작점과 x,y,n까지의 숫자를 비교했을 때 같은지 확인한다.

# 시작점과 반복문으로 돈 입력값의 숫자가 같다면, 초기화 한 result 리스트에 append 한다.

# 시작점과 반복문으로 돈 입력값의 숫자가 다르다면, 분할 후 한면씩 반복문을 돈다.

# 반복문을 돌리면서 전체 색이 같아지는 순간에 초기화 한 result 리스트에 append 한다.

4분할 후

 

분할된 면 중에 첫 면 먼저 해결/ 여기서도 해결 안되면

 

더 작게 4분할 하고 다시 그 분할면 중에 첫 면 먼저 해결될때까지 반복문 돌림.

 

   문제풀이   

import sys

N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
# [[1, 1, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 1]]
result = []     # 0이나 1만 가지고 있는 색종이 생기면 추가

def solution(x, y, N):
  num = paper[x][y]   # 변수에 각 정사각형 종이의 자리 할당 / paper[0][0] = 1
  for i in range(x, x+N):  # 시작점과 숫자가 같은지 반복문을 돌면서 확인
    for j in range(y, y+N):
      if num != paper[i][j]:  # 숫자가 다르면 4분할
        solution(x, y, N//2)
        solution(x, y+N//2, N//2)
        solution(x+N//2, y, N//2)
        solution(x+N//2, y+N//2, N//2)
        return
  if num == 0:
    result.append(0)
  else: # color == 1
    result.append(1)


solution(0,0,N)
print(result.count(0))  # result의 0의 개수 -> 하얀 종이 개수
print(result.count(1))  # result의 1의 개수 -> 파란 종이 개수