[Baekjoon/🥈SilverⅢ] 2630: 색종이 만들기

Intro

• 문제의 핵심은 색종이를 자르는 방식이다!

  • 자르고자 하는 색종이가 하나의 색으로 이루어져 있지 않다면 4등분한다.

  • 잘라진 종이가 모두 흰색 혹은 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

👩 문제에서 제시한 예시의 색종이를 위 방식대로 자른다면 최종적으로 9개의 흰색 종이와 7개의 파란 종이로 나뉘어진다.

문제의 예시 입력과 출력은 다음과 같다.

접근 방법🙋‍♀️

👩 그렇다면 문제에 어떻게 접근해야 할까?

색종이를 자르는 과정을 자세히 살펴본다면 다음과 같이 문제를 일반화 할 수 있다.

• 주어진 종이에 두 색이 모두 존재한다면 4등분을 진행한다.

• 주어진 종이에 하나의 색만 존재한다면 해당 색의 종이 수를 하나 증가시킨다.

• 👩 만약 4등분을 진행했다면 나누어진 각 종이에 대해서도 위 두 과정을 반복한다.
  • 4등분 시, 정사각형의 시작점의 인덱스(x,y)를 기준으로 재귀를 호출해 위 과정을 반복한다.

결론적으로 우리는 분할정복을 통해서 문제를 해결할 수 있게 된다!

큰 문제를 작은 문제들로 나눠 그 문제들을 해결함으로써 하나의 큰 문제를 해결할 수 있게 되는 것이다!!

👩 n= 4일 경우 어떻게 진행되는지 그 예를 그림으로 살펴보자!

Algoritm👩‍💻

위 방식을 적용해 알고리즘을 작성해보자!

#21.10.18
import sys

# 흰색, 파란색 색종이의 개수를 구하는 함수
def getCount(x, y, num):
  global colors, count
  # 기준이 되는 첫 시작점의 색깔
  chk = colors[x][y]
  for i in range(x, x+num):
    for j in range(y, y+num):

      # 하나라도 다른 색이 존재할 경우, 4등분 진행!
      if(chk != colors[i][j]):
        size = num//2
        getCount(x, y, size)
        getCount(x+size, y, size)
        getCount(x, y+size, size)
        getCount(x+size, y+size, size)
        return

  # 모두 같은 색깔인 경우      
  count[chk] += 1
  return

n = int(input())
colors = []
count = [0, 0]
for i in range(n):
  colors.append(list(map(int, sys.stdin.readline().rstrip().split())))
getCount(0, 0, n)
print(count[0])
print(count[1])

위 과정을 정확히 이해했다면 코드는 아마 무척 쉽게 이해될 것이다!!

따라서 별도의 설명을 추가하지 않겠다.

👩 해당 문제를 풀어보면서 분할정복 부분에 대해서 조금 부족하다는 것을 느끼게 되었다. 관련된 문제를 더 풀어보며 그 방식을 정확히 익혀야겠다!

그럼 여기서 이만 마무리하도록 한다!

끝! ~(˘▾˘~)

📃참고

• https://happylsm76.tistory.com/entry/%EB%B0%B1%EC%A4%80-2630%EB%B2%88%EC%83%89%EC%A2%85%EC%9D%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0-with-Python
• https://hyo-ue4study.tistory.com/235