[백준 알고리즘] - 색종이 만들기 (2630번) with Python

📎 간략한 문제 정리

• 위의 그림처럼 한 변의 길이가 2의 거듭제곱꼴인 N의 정사각형(NxN)이 존재합니다. 이 사각형은 길이가 1인 단위 정사각형으로 이루어져 있으며 색깔을 가집니다. 만약 이 정사각형이 모두 색깔이 같다면 자르지 않지만, 하나라도 색깔이 다른 부분이 있다면 종이 가로 세로의 가운데를 잘라 4등분하여 위의 작업을 반복합니다. 모든 작업이 완료되면 흰 종이(0으로 마킹)의 개수과 파란 종이(1로 마킹)의 개수를 출력합니다.

📈 문제 분석

• 전형적인 분할 정복 문제입니다. 특정 시점에서 조건에 맞는지 확인(모두 같은 색)한 후, 조건에 맞으면 추가 작업을 진행하지 않고, 조건을 만족하지 않으면 재귀적으로 문제를 다시 해결해나가는 구조입니다. Merge Sort(병합 정렬)처럼 개념으로 배울 때의 분할 정복과 달리, 문제를 무조건 최소단위까지 분할한 후 정복해나가는 구조가 아니라 분할에 조건을 주어 분할하는 문제입니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 우선 순회하며 전체 색깔이 같은지 확인할 함수가 필요합니다. 처음으로 떠오른 방식은 두가지가 있습니다.

  paper_color = paper[0][0]
  for i in range(K):
   for j in range(K):
     if paper[i][j] != paper_color: return False
  return True

  위의 구조로 반드시 존재하는 첫번째 항의 색깔을 기준으로 모든 순회를 하다가 하나라도 다른 색깔이 나오면 모두 같은 색이 아니라는 조건입니다. 두번째 방식은 아래와 같습니다.

  K = len(paper)
  total = 0
  for i in range(K):
   total += sum(paper[i])
  return True if total == 0 or total == K**2 else False

  위의 풀이는 모든 요소가 0 또는 1이라는 점에서 생각한 것으로 모든 요소가 같다면 반드시 모든 종이에 적힌 숫자의 합은 0 또는 K의 제곱이 되어야 합니다. 이 이외에 다른 상황은 있을 수 없습니다. 하지만 이렇게 작성하면 결국 모든 사각형의 요소를 전부 확인하는 것이므로 처음의 생각과 크게 다르지 않습니다. 오히려 중간에 멈추는 위의 코드보다 느리다고 할 수 있습니다. 그래서 이 코드에 break 조건을 생각해보면

  K = len(paper)
  total = 0
  for i in range(K):
   total += sum(paper[i])
   if total != 0 and total != (i+1) * K: return False
  return True 

  위의 코드의 경우 중간에 어느 한 줄에서라도 다른 요소가 나올 경우 False를 반환하고, 문제가 없을 경우 True를 반환하게 됩니다. 속도는 세가지 모두 O(N^2)이지만 중간에 멈추는 코드가 있는 1, 3번의 코드에 비해 2번 코드는 비효율적이고 3번 역시 그 줄을 모두 합하는 연산을 하기 때문에 오히려 1번 코드보다 더 많은 연산을 한다고 볼 수 있습니다. 큰 차이는 아니지만 그래서 1번의 연산을 채택하여 해당 사각형의 종이가 모두 같은 종류인지 확인하기로 정했습니다.

• 두번째로 필요한 것은 결과를 담을 변수입니다. 종이를 자르는 함수는 재귀적으로 동작할 것이기 때문에 함수 바깥에 함수 실행에 관계없이 유지될 변수가 필요합니다. 굳이 함수 안에 넣는다면 global로 선언하여 전역적으로 사용할 수 있지만, 그럴 필요성이 없어 외부에 변수를 선언하기로 했습니다. 색깔 자체가 리스트에 숫자 0, 1로 표현되어 있어 인덱스로 바로 접근 가능하게 리스트로 선언하였습니다.

  paper_count = [0, 0] # 0번 white, 1번 blue

• 종이를 확인한 후 종이가 같은 색이면 해당 색깔의 카운트를 추가하고, 아니면 종이를 자를 함수가 필요합니다. 여기에서는 재귀적인 작업이 필요합니다.

💻 풀이한 코드

• 최종적으로 작성한 코드는 아래와 같습니다.

  from sys import stdin
  input = stdin.readline
  N = int(input())
  paper = [list(map(int, input().split())) for _ in range(N)]
  paper_count = [0, 0]
  def is_same_color(x:int, y:int, K:int) -> bool:
      paper_color = paper[x][y]
      for i in range(x, x+K):
          for j in range(y, y+K):
              if paper[i][j] != paper_color: return False
      return True
  def check_paper(x, y, K):
      if is_same_color(x,y,K): paper_count[paper[x][y]] += 1
      else:
          half = K//2
          xx = x + half
          yy = y + half
          check_paper(x, y, half)
          check_paper(xx, y, half)
          check_paper(x, yy, half)
          check_paper(xx, yy, half)
  check_paper(0, 0, N)
  for i in range(2):
      print(paper_count[i])

📝 해결 과정에서 만난 문제, 고민들

• 최종 코드를 보면 처음 생각한 것과 방향이 달라진 것을 볼 수 있습니다. 문제들을 하나씩 정리해보겠습니다.

  1. 2차원 배열 슬라이싱:

     함수를 생성할 때 paper 리스트 자체를 받는 것으로 해서, 그 리스트를 잘라서 다시 넣을 생각으로 코드를 작성했었습니다. 하지만 이렇게 할 경우, 2차원 배열을 슬라이싱 할 수 없다는 파이썬의 문제가 드러납니다. 종이를 자르는 행위는 2차원 배열을 슬라이싱 하는 것으로, Numpy의 기능처럼 간단하게 해결할 수 없기 때문에 1/4 크기의 배열을 선언해준 후 모든 요소를 직접 넣어줘서 partial paper를 만들어줘야하는 문제점이 있었습니다. 그래서 왼쪽 가장 위, 2차원 배열의 시작점과 한 변의 길이를 넣는 함수로 다시 만들었습니다.

  2. 로직을 작성하던 중, 문제가 발생했을 때 수정 방향을 로직의 역방향으로 타고 올라가는 문제:

     위에서 언급한 것처럼, 작성 중 문제를 발견해 수정할 때 아래에서부터 수정하는 작업을 진행했습니다. 그러다보니 실행시 문제가 어디서 발생한지 정확히 알지 못했고 이 경우에는 recursion 깊이 오류가 있었습니다(Overflow). 그래서 sys의 setrecursionlimit을 사용했지만 해결되지 않아 print로 콘솔을 본 뒤 문제를 깨닫게 되었습니다. 코드를 작성하던 중 문제가 생기면 위에서부터 전체 로직을 다시 살펴볼 필요가 있습니다. 문제가 생긴 부분만 보거나, 그 부분부터 시작하여 역으로 올라가면 시간이 오히려 더 오래걸리거나 문제를 해결 못할 수 있습니다.

  3. 구현하는 코딩을 하는 것과 알고리즘의 괴리:

     구현하는 코딩을 할 때에는 네이밍, 객체 지향적인 고민을 많이 합니다. 하지만 알고리즘을 짤 때에는 효율성을 기준으로 생각해야하는 것을 알고 있지만 짜는 순간에 고민을 많이 하게 됩니다. 위의 코드의 경우에도 half = K//2 같은 경우 공간 효율성에서 굳이 필요하지 않고 xx, yy의 정의 역시 마찬가지입니다. 하지만 리딩할 때에 훨씬 도움이 되므로 선언을 해주었는데 이런 경우 쓸데없는 고민의 시간이 있습니다. 비록 알고리즘이지만 제 스스로 나중에 코드 리팩토링의 필요가 있을 수 있으므로 너무 큰 차이가 아니라면 읽기 쉬운 코드를 작성하는 습관을 알고리즘에서도 유지할 필요가 있을 것으로 생각됩니다.

색종이 만들기