문제

BOJ 2630: 색종이 만들기 https://www.acmicpc.net/problem/2630

풀이

조건

• 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 색종이로 나눈다.
• 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
• 하얀색 색종이와 파란색 색종이의 개수를 구한다.

풀이 순서

• 분할 정복을 재귀 함수를 통해 구현했다.
• 1장 짜리가 되면 종료한다.
• 1장 짜리가 아니면 모두 같은 색으로 이뤄져 있는지 확인한다.
  • 모두 같은 색이면 종료한다.
  • 다른 색이 섞여 있으면 4분할 하여 4 덩어리를 재귀호출한다.

코드

Python

import sys

N = int(sys.stdin.readline().rstrip())

board = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]

result = 0  # 전체 분할된 종이 수
blue = 0  # 파란 색종이 수


# 분할 정복 함수
# 왼쪽 위 행, 열 / 오른쪽 밑 행, 열 -> 파라미터로 전달
def separate(sr, sc, er, ec):
    global result, board, N, blue

    # 1장 짜리면 색 구분하고 종료
    if sr == er and sc == ec:
        if board[sr][sc] == 1:
            blue += 1
        result += 1
        return

    # 여러 장일 때 모두 같은 색인 종이인 지 확인
    temp = board[sr][sc]  # 모두 같은 색인지 확인할 때 쓸 기준 색
    flag = True  # True -> 모두 같은 색 / False -> 하나 라도 다른 색 있음
    for i in range(sr, er + 1):
        for j in range(sc, ec + 1):
            # 다른 색 있으면 break
            if board[i][j] != temp:
                flag = False
                break
    # 모두 같은 색으로 이뤄진 종이면 종료
    if flag:
        if temp == 1:
            blue += 1
        result += 1
        return
    # 다른 색이 있는 덩어리면 재귀 호출
    else:
        # 절반으로 자름
        midR = (sr + er) // 2
        midC = (sc + ec) // 2

        # 4덩이로 자르고 재귀 호출
        separate(sr, sc, midR, midC)
        separate(sr, midC + 1, midR, ec)
        separate(midR + 1, sc, er, midC)
        separate(midR + 1, midC + 1, er, ec)


# main 메소드
def solution():
    global N, board, result, blue

    # 분할 정복 시작
    separate(0, 0, N - 1, N - 1)

    print(result - blue)
    print(blue)


solution()

정리

• 분할 정복을 재귀로 구현하는 연습을 하기 좋은 문제인 것 같다.