백준 - 2630번 색종이 만들기 python 문제풀이 [Hellfer]

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

2630번: 색종이 만들기

🔷 알고리즘 분류 - 분할 정복, 재귀   난이도 - 실버 2

분할 정복(Divide and Conquer) 알고리즘은 문제를 더 작은 부분으로 분할하여 해결하는 방법을 의미합니다. 

이 알고리즘은 크게 세 단계로 이루어져 있습니다.

1. 분할(Divide): 주어진 문제를 작은 부분 문제(sub-problems)로 분할합니다. 이때 분할된 작은 문제는 원래 문제와 동일한 형태를 가집니다.

2. 정복(Conquer): 분할된 작은 문제를 각각 해결합니다. 작은 문제의 크기가 충분히 작아질 때까지 이 과정을 반복하며, 문제의 크기가 충분히 작다면 직접 해결할 수 있습니다.

3. 결합(Combine): 정복한 작은 문제의 해결책을 결합하여 원래 문제의 해결책을 얻습니다.

분할 정복 알고리즘은 이런 방식으로 문제를 쪼개어 가면서 해결하므로, 복잡한 문제를 간단하게 해결하는 데 유용합니다.

🔶문제 풀이 - 분할 정복 알고리즘을 이용한 풀이

import sys
input=sys.stdin.readline

n=int(input()) # 종이의 크기를 입력받습니다.
graph=[list(map(int,input().split())) for _ in range(n)] # 종이의 정보를 입력받아 2차원 리스트를 생성합니다.
white=0 # 흰색 종이의 개수를 저장할 변수를 선언합니다.
blue=0 # 파란색 종이의 개수를 저장할 변수를 선언합니다.

def check(x,y,n): # 현재 종이가 모두 같은 색으로 이루어져 있는지 확인하고, 그렇지 않다면 종이를 4등분하여 재귀적으로 확인하는 함수입니다.
    global white, blue # 전역 변수인 white와 blue를 사용하기 위해 global 키워드를 사용합니다.
    paper=graph[x][y] # 현재 종이의 첫 번째 셀의 색을 저장합니다.
    for i in range(x,x+n): # 현재 종이의 모든 셀을 순회합니다.
        for j in range(y,y+n):
            if paper != graph[i][j]: # 현재 셀의 색이 첫 번째 셀의 색과 다르다면, 현재 종이는 같은 색으로 이루어져 있지 않습니다.
                check(x,y,n//2) # 현재 종이를 4등분하여 각 부분을 재귀적으로 확인합니다.
                check(x,y+n//2,n//2)
                check(x+n//2,y,n//2)
                check(x+n//2,y+n//2,n//2)
                return # 재귀 호출을 한 후에는 현재 함수를 종료합니다.
    if paper == 0: # 모든 셀의 색이 첫 번째 셀의 색과 같다면, 현재 종이는 모두 같은 색으로 이루어져 있습니다. 이 경우, 종이의 색에 따라 흰색 또는 파란색 종이의 개수를 증가시킵니다.
        white+=1
    else:
        blue+=1
        
check(0,0,n) # (0, 0) 위치에서 시작하는, 크기가 n인 종이를 확인합니다.
print(white) # 흰색 종이의 개수를 출력합니다.
print(blue) # 파란색 종이의 개수를 출력합니다.

🔶 문제 이해하기

1. check(x, y, n // 2): 현재 종이를 왼쪽 위를 기준으로 4 등분했을 때, 첫 번째 부분(왼쪽 상단)을 검사하기 위한 재귀 호출입니다.

x와 y는 그대로 유지되고, 종이의 크기는 절반으로 줄어듭니다.

2. check(x, y + n // 2, n // 2): 현재 종이를 4 등분했을 때, 두 번째 부분(오른쪽 상단)을 검사하기 위한 재귀 호출입니다.

x는 그대로 유지되고, y는 n // 2 만큼 증가하여 오른쪽 부분을 검사할 수 있게 됩니다. 종이의 크기는 절반으로 줄어듭니다.

3. check (x + n // 2, y, n // 2): 현재 종이를 4 등분했을 때, 세 번째 부분(왼쪽 하단)을 검사하기 위한 재귀 호출입니다. y는 그대로 유지되고, x는 n // 2 만큼 증가하여 아래쪽 부분을 검사할 수 있게 됩니다. 종이의 크기는 절반으로 줄어듭니다.

4. check (x + n // 2, y + n // 2, n // 2): 현재 종이를 4 등분했을 때, 네 번째 부분(오른쪽 하단)을 검사하기 위한 재귀 호출입니다.

x와 y 모두 n // 2 만큼 증가하여 오른쪽 아래 부분을 검사할 수 있게 됩니다. 종이의 크기는 절반으로 줄어듭니다.

이렇게 재귀 호출을 통해 4 등분된 종이의 각 부분을 검사하게 됩니다. 이 과정을 통해 주어진 종이가 모두 같은 색인지를 확인하고, 같은 색이 아니라면 계속해서 종이를 4 등분하여 검사하는 과정을 반복하게 됩니다.

 

check(x,y,n//2) # 현재 종이를 4등분하여 각 부분을 재귀적으로 확인합니다.
check(x,y+n//2,n//2)
check(x+n//2,y,n//2)
check(x+n//2,y+n//2,n//2)

 

예를 들어, 8x8 크기의 종이가 있고, 현재 (0, 0) 위치에서부터 검사를 시작한다고 가정해 봅시다.

 

그리고 이 종이는 다음과 같이 색칠되어 있다고 가정합니다. (0은 흰색, 1은 파란색)

 

0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

 

1. 초기에 (0, 0) 위치의 셀을 확인하면 흰색입니다. 이 색을 기준으로 종이를 검사합니다.

2. 종이의 셀을 순회하다가 (0, 4) 위치의 셀이 파란색인 것을 확인하고, 현재 검사하는 종이를 4 등분하여 각 부분을 재귀적으로 검사합니다.

 

이때 4 등분한 종이들은, 왼쪽 위 부분이 (0, 0)에서 시작하고 크기가 4x4, 오른쪽 위 부분이 (0, 4)에서 시작하고 크기가 4x4, 왼쪽 아래 부분이 (4, 0)에서 시작하고 크기가 4x4, 오른쪽 아래 부분이 (4, 4)에서 시작하고 크기가 4x4인 종이들입니다.

3. 이렇게 분할된 종이들에 대해 같은 과정을 반복합니다. 만약 다시 다른 색의 셀을 발견하면, 그 종이를 다시 4 등분하여 검사합니다.

 

이런 식으로, 코드는 종이의 색이 일치하지 않으면 계속해서 종이를 4 등분하여 재귀적으로 검사하고, 종이의 색이 모두 일치하면 그 색의 카운트를 증가시킵니다.

 

🤗파이팅입니다~ 여러분!!🤗