백준 알고리즘 No.2630 색종이 만들기

in Study #Algorithm #Python

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

(중략)

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.



체감 난이도: ★★

백준 문제들을 계속 풀다보니 정말 다양한 알고리즘이 존재함을 느낀다..

Code

def square(x, y, n):
    global white, blue
    color = paper[x][y]               # 첫번째 칸의 색상

    for i in range(x, x+n):
        for j in range(y, y+n):       # 색종이의 모든 칸 순회
            if color != paper[i][j]:  # 색종이 4분할
                square(x, y, n//2)                # 왼쪽 위
                square(x, y + n//2, n//2)         # 오른쪽 위
                square(x + n//2, y, n//2)         # 왼쪽 아래
                square(x + n//2, y + n//2, n//2)  # 오른쪽 아래
                return

    if color == 0:
        white += 1
    else:
        blue += 1

N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
white, blue = 0, 0

square(0, 0, N)
print(white, blue, sep='\n')

Solution

분할 정복: 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법


✔ def square(x, y, n)

  • 함수의 인수 x, y는 순회를 시작할 좌표, n은 순회할 정사각형의 변의 길이
  • color = paper[x][y]: 순회를 시작할 칸, 즉 첫번째 칸의 색상을 저장한다.
  • 그 후, 시작점 (x, y)에서 (x+n, y+n)까지 반복문을 돌면서 해당 영역의 모든 색상을 확인한다.
  • if color != paper[i][j]: 만약 현재 확인중인 색이 시작점의 색과 다르다면, 현재 영역을 4분할하여 재귀적으로 확인한다.
  • 마지막으로 영역의 색을 확인하여 하얀색 색종이와 파란색 색종이의 개수를 저장한다.


혹시 더 좋은 알고리즘 풀이가 있다면 언제든 댓글로 알려주세요 😃