[백준 2630번] 색종이 만들기(Python/파이썬)

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

2630번: 색종이 만들기

정사각형안에 1만 존재하거나, 0만 존재하면 색종이를 카운트 하는 문제이다.

알고리즘은 분할정복이라고 나와있긴하지만, 문제를 분할한 다음에 다시 합치는 과정이 없기 때문에 그냥 재귀라고 생각해도 충분히 풀수 있는 문제이다.

분할정복을 더 알아보고 싶다면 파이썬의 정렬모듈로 사용되고 있는 병합정렬을 공부해보면 좋다.

 

풀이는 처음 시작점의 숫자를 저장해두고 탐색하다가 처음 저장해둔 숫자와 다르면 4방면으로 분할하고 리턴해주면 된다.

리턴은 단순히 함수를 끝내기 위해 사용했는데, 이걸 안하면 처음 저장해놓은 숫자와 달라도 반복문이 끝나면 색종이 개수가 카운트 되기 때문에 모두 한숫자로 이루어지지 않으면 4방면으로 나누고 숫자가 카운트 되기전에 return으로 함수를 끝내줘야 한다.코드와 함께 다시 천천히 읽어보면 이해하기 쉬울것이다.

 

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N = int(input())
colored_paper = []
for _ in range(N):
  tmp = list(map(int, input().split()))
  colored_paper.append(tmp)
cnt_1 = 0
cnt_0 = 0

def slice(x,y,n):
  global cnt_1, cnt_0
  tmp = colored_paper[x][y]
  for i in range(x,x+n):
    for j in range(y,y+n):
      if colored_paper[i][j] != tmp:
        slice(x,y,n//2)
        slice(x+n//2,y,n//2)
        slice(x,y+n//2,n//2)
        slice(x+n//2,y+n//2,n//2)
        return
  else:
    if tmp == 0:
      cnt_0 += 1
    else:
      cnt_1 += 1

slice(0,0,N)
print(cnt_0)
print(cnt_1)

 

 

재귀를 익숙하게 하기 위해 기반이 되는 문제이다.