[백준 2630 파이썬] 색종이 만들기 (실버3, 분할 정복)

알고리즘 유형 : 분할 정복
풀이 참고 없이 스스로 풀었나요? : O (풀이 참고 후 최적화)

https://www.acmicpc.net/problem/2630

SOLVE 1

제너레이터, check 변수 활용 풀이

import sys
input = sys.stdin.readline

N = int(input())
confetti = [list(map(int, input().split())) for _ in range(N)]

# 제너레이터
def quadrant(x, y, size):
    x1 = x + size
    y1 = y + size
    yield x, y
    yield x, y1
    yield x1, y
    yield x1, y1

def slicing(x, y, size):
    if size == 1:
        return (0, 1) if confetti[x][y] else (1, 0)
    
    check = confetti[x][y]
    isColor = True
    
    # size x size에서, for를 돌면서 맨 첫 번째 한 요소와 다른 것이 하나라도 있으면,
    # 전체가 1이나 0이 아닌 박스이므로, isColor를 거짓으로 할당하고 밑 조건문에서
    # 분할 구문 실행
    # 아니면 첫 항의 값에 따라 하양, 파랑의 개수를 나타내는 값 리턴
    for i in range(x, x+size):
        for j in range(y, y+size):
            if check != confetti[i][j]:
                isColor = False
                break

    if isColor:
        if check:
            return 0, 1
        else:
            return 1, 0
    else:
        w, b = 0, 0
        # 정의해 둔 제너레이터(4분할 좌표) 돌면서 하양, 파랑 개수 수합 후 리턴
        for u, v in quadrant(x, y, size//2):
            w1, b1 = slicing(u, v, size//2)
            w += w1
            b += b1
        return w, b

w, b = slicing(0, 0, N)
print(w)
print(b)

SOLVE 2

check 변수 없이, 제너레이터 for문 만으로 구성한 간결한 풀이

import sys
input = sys.stdin.readline

N = int(input())
confetti = [list(map(int, input().split())) for _ in range(N)]

def quadrant(x, y, size):
    x1 = x + size
    y1 = y + size
    yield x, y
    yield x, y1
    yield x1, y
    yield x1, y1

def slicing(x, y, size):
    if size == 1:
        return (0, 1) if confetti[x][y] else (1, 0)
    
    w, b = 0, 0
    size_sub = size // 2
    for u, v in quadrant(x, y, size_sub):
        w1, b1 = slicing(u, v, size_sub)
        w += w1
        b += b1
    # 박스가 전체 1이든 0이든 상관없이 끝까지 재귀를 돔.
    # 다 끝나고 둘 중 하나의 값이 0인 경우는, 전체가 1이거나 0이라는 뜻임. 그걸 조건문으로
    # 걸러주고, 이외의 경우에는 그대로 4분할해서 계산한 하양, 파랑 값 리턴
    if w == 0:
        return 0, 1
    elif b == 0:
        return 1, 0
    return w, b

w, b = slicing(0, 0, N)
print(w)
print(b)

SOLVE 1) 풀이 요약 (제너레이터, check 변수 활용 풀이)

1. 처음에는 제너레이터없이, 4분할 했을 때 각 좌표와 새로운 사이즈로 slicing 호출을 4개 일일이 작성했는데,

   다른 사람 풀이보니까 제너레이터를 쓰길래, 더 간결하고 편해보였음

2. 핵심 원리는 분할 정복.

   어떤 박스의 하양, 파랑 그룹 수를 구하기 위해, 박스를 4분할해서 그 각각의 박스에서 하양 파랑 그룹 수를 구하고 싹 다 더해줌.

3. 다만 그 전에, 박스 전체가 하양이거나 파랑인 경우를 먼저 걸러줌. 4분할 재귀 호출의 깊이와 횟수를 줄이기 위해서임.

   size x size 크기 박스를 for 돌면서, 박스의 맨 첫 번째 요소와 순회 요소를 계속 비교해나가며 하나라도 다른 것이 있다면 그 박스는 전체가 하양 또는 파랑일 수 없는 것이므로 isColor = False

4. isColor = True면 check 값에 따라 하양, 파랑 개수를 알맞게 리턴해주면 되고, False이면 4분할 코드로 ㄱㄱ

5. 4분할, 즉 4번 재귀 호출을 보다 간결하고 쉽게 작성하기 위해, 제너레이터 함수 정의 및 사용.

   제너레이터는 함수로 정의하는데, 이 함수의 리턴 값은 선언한 yield를 순서대로 첫 번째 yield, 두 번쨰 yield, ...등으로 이루어진 iterable한 객체가 됨. 즉 for 돌 때 yield로 선언한 값들을 순서대로 돌게 된다.

SOLVE 2 풀이 요약 (check 변수 없이, 제너레이터 for문 만으로 구성한 간결한 풀이)

1. check 변수 활용 없이, 제너레이터 for문 만으로 구성할 수도 있다.

   이 경우 전체가 하양박스냐 파랑박스냐 판별하는 것 없이, 무조건 어떤 경우에서든 size=1까지 끝까지 재귀를 돌아버리기에, 재귀 깊이와 횟수가 좀 더 많아진다. 하지만 코드는 훨씬 짧고 간결해진다는 장점이 있다.

​

배운 점, 어려웠던 점

• 제너레이터 문법에 대해 배웠다.

• 처음에는 global 문법을 써서 전역 변수에 blue, white값을 4분할 for 돌 때마다 거기에 더해주는 방식으로 풀었는데, global을 남용하면 안좋다는 얘기를 들었어서, 하양, 파랑의 개수를 튜플이나 다인자 형태로 반환하는 식으로 코드를 수정했다.