[백준 2630] 색종이 만들기

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

---

접근

분할정복이 이해가 되지않아 문제를 풀어보면서 이해하고자 했다.

분할정복은 큰 문제를 풀기보다 작은 문제들로 나누고 작은 문제부터 해결해나가는 것이라고 이해했다.

그래서 이 문제에서 어떻게 분할할지를 신경썼다. 다른 사람들의 풀이를 참고하였는데 입력예시처럼 8x8 크기의 맵이 들어온다고 해보자.

 

8x8의 크기를 4x4의 크기로 나눠 네 개의 맵을 만든다. 그리고 다시 4x4를 2x2로 나눈다.

1x1이 되었을 때 까지 나눌 수 있다면 나눈다.

 

여기서 각각의 크기의 맵에는 같은 색이 존재해야하기 때문에 처음 기준이 되는 좌표의 색과 다른 좌표의 색이 다를 때 맵의 크기를 나눈다. 그리고 해당 크기의 맵에 색이 모두 동일 했을 때 카운트를 하도록 한다.

 

구현

아래의 코드는 분할정복을 하는 함수이다.

처음에 입력된 좌표를 기준 color로 정하여 해당 color와 같은 색만 있는지 검사한다.

만약 다른 색이 존재한다면 check를 False로 변경한다.

또한 색이 다르다면 계속해서 크기를 반으로 나눠서 동일한 로직을 실행한다.

만약 해당 맵에서 색이 모두 동일 했을 때 색에 따라서 하얀색과 파란색의 개수를 카운트하도록 한다.

def partition(y, x, N):
    global blue, white
    color = matrix[y][x]
    check = True

    for i in range(y, y+N):
        if not check:
            break
        for j in range(x, x+N):
            if color != matrix[i][j]:
                check = False
                partition(y, x, N//2)
                partition(y, x+N//2, N//2)
                partition(y+N//2, x, N//2)
                partition(y+N//2, x+N//2, N//2)
                break
    if check:
        if color:
            blue += 1
        else:
            white += 1

---

전체 코드

import sys
sys.stdin = open("input.txt")

def partition(y, x, N):
    global blue, white
    color = matrix[y][x]
    check = True

    for i in range(y, y+N):
        if not check:
            break
        for j in range(x, x+N):
            if color != matrix[i][j]:
                check = False
                partition(y, x, N//2)
                partition(y, x+N//2, N//2)
                partition(y+N//2, x, N//2)
                partition(y+N//2, x+N//2, N//2)
                break
    if check:
        if color:
            blue += 1
        else:
            white += 1
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
blue = white = 0
partition(0, 0, N)
print(white)
print(blue)