[ 백준 ] 2630 색종이 만들기 파이썬python 풀이

 

 

// 문제 요약

 

위와 같이 절반씩 나누어서 만들 수 있는 가장 큰 정사각형 종이를 원할때

 

얻을 수 있는 종이 중에서 파란색과 흰색의 수는 각각 몇장씩인지 출력하여라

 

 

 

// 사고

 

분할 정복을 사실상 한번도 구현해보지 않은 상태에서 만난 문제

 

처음에는 종이를 나눈 횟수에 따라 정사각형의 시작점과 끝점을 구하고

 

그 안에서 탐색을 다시 하는 함수를 탑다운으로 짜고 있었는데

 

짜면서 바로 아 이방법으로는 안되겠다 하는 부분이 너무 많아서

 

그냥 풀이를 바로 찾아봤다.

 

이 풀이는 분할정복 중에서도 4개로 나뉘는 방식이라 하여

 

쿼드트리 방식이라고 한다.

 

코드를 보자.

 

 

 

// 풀이

 

https://url.kr/1zmqlt

hyun06000/coding_test_study_with_python

 

### input

N = int(input())

paper = []
for _ in range(N):
    paper.append(list(map(int, input().split(' '))))

### solution

# quard tree

blue = 0
white = 0
def quard_tree(i, j, n, paper):
    global blue, white
    default_color = paper[i][j]
    for _i in range(i, i + n):
        for _j in range(j, j + n):
            if paper[_i][_j] != default_color:
                quard_tree(i,          j,          n // 2, paper)
                quard_tree(i + n // 2, j,          n // 2, paper)
                quard_tree(i,          j + n // 2, n // 2, paper)
                quard_tree(i + n // 2, j + n // 2, n // 2, paper)
                return
    if default_color:
        blue += 1
    else:
        white += 1
    return

quard_tree(0, 0, N, paper)

### print
print(white)
print(blue)

 

잘보면 4방향으로 움직이는 dfs 풀이와 많이 닮아있다.

 

쿼드트리라는 말그대로 원하는 조건을 충족하지 못하면

 

4개로 분할하여 시작점과 분할 구간을 각각 할당하고

 

재귀적으로 풀이를 하되 조건문이 있으니 백트래킹이 되도록 짜둔 코드다.

 

알면 금방 생각나지만 모르면 한참을 헤매야 한다.

 

 

 

// 참고

https://claude-u.tistory.com/268

#217 백준 파이썬 [2630] 색종이 만들기 - 분할 정복