[분할정복/DQ] 백준 2630 색종이 만들기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2630번: 색종이 만들기

 

 

 

2. 문제 풀이

 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 문제입니다. 정사각형의 색종이에 하얀색과 파란색이 섞여 있을 경우, 분리될 때까지 4분할을 합니다.

 입력으로 주어지는 색종이의 크기는 2, 4, 8, 16, 32, 64, 128 중 하나입니다.

 

 

2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

[Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘

 분할정복 문제입니다. 반복해서 문제(입력범위)를 분할하고, 동일한 알고리즘으로 색종이의 색을 판별합니다. (병합하는 과정은 없습니다.)

 분할정복 문제를 풀 때 주의할 점이 있습니다. 동일한 함수(알고리즘)로 문제를 분할하고, 부분 문제들을 풀이해야 합니다. 이 과정에서 주로 재귀적 방법이 쓰이게 됩니다.

 

 

 

3. 코드

N = int(input())
colorPaper = []
for i in range(N):
    colorPaper.append(list(map(int, input().split())))

 색종이의 크기와, 색종이의 상태를 입력으로 받습니다. N*N으로 2차원 리스트를 입력받아야 합니다.

append() 함수를 사용하면 리스트 안에 리스트를 삽입할 수 있습니다.

 

 

# 같은 색종이 판별기
# 모두 더했을 때 0 = 전부 0 / 모두 더했을때 N = 전부 1
def isSamePaper(x,y,n):
    _sum = 0
    for i in range(x, x+n):
        for j in range(y, y+n):
            _sum += colorPaper[i][j]
    if _sum == 0:
        return 0 # 하얀색
    elif _sum == n**2:
        return 1 # 파란색
    else:
        return -1 # 섞임

 먼저 색종이의 색깔을 판별하는 함수를 작성합니다. 0이면 하얀색이고, 1이면 파란색입니다. 따라서 해당 영역의 리스트 합이 0이면 하얀색이고, n^2이면 파란색입니다. 둘 다 해당하지 않으면 하얀색과 파란색이 혼재되어 있는 경우입니다.

 

 

# 분할 정복
def searchPaper(a, b, n):
    x = isSamePaper(a,b,n)
    if x == -1: # 섞였을 경우, 4분할
        searchPaper(a, b, n//2)
        searchPaper(a + n//2, b, n//2)
        searchPaper(a, b + n//2, n//2)
        searchPaper(a + n//2, b + n//2, n//2)
    elif x == 0: # 모두 하얀색
        global white
        white += 1
        #print("white: ",white, f"({a},{b}), {n}")
        return
    elif x == 1: # 모두 파란색
        global blue
        blue += 1
        #print("blue: ",blue, f"({a},{b}), {n}")
        return

 분할하고 판별하는 알고리즘을 작성합니다. 섞였을 경우에는 입력범위를 4분할로 나누어서 재귀함수를 실행합니다. 섞이지 않았을 때에는 해당 색깔의 개수를 올리고 마칩니다.

 

 

white = 0
blue = 0

searchPaper(0,0,N)
print(white)
print(blue)

 이제 만들어진 분할정복 알고리즘을 사용하기만 하면 됩니다. 전역변수로 사용할 white와 blue를 초기화하고 분할정복 알고리즘을 실행합니다.