백준 - 1780번 종이의 개수 python 문제풀이 [Hellfer]

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

1780번: 종이의 개수

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

 

분할 정복(Divide and Conquer) 알고리즘은 문제를 더 작은 부분으로 분할하여 해결하는 방법을 의미합니다. 
이 알고리즘은 크게 세 단계로 이루어져 있습니다. 

 

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

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

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

 

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

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

import sys
input=sys.stdin.readline  # sys.stdin.readline은 입력 속도를 높여주는 기능입니다.

# 사용자로부터 첫 번째 숫자를 입력 받아 정수로 변환한 후 n에 저장합니다. 이는 그래프의 크기를 의미합니다.
n=int(input())

# 사용자로부터 n*n 크기의 2차원 배열을 입력 받습니다.
graph=[list(map(int,input().split())) for _ in range(n)]

# 각 숫자의 개수를 저장할 변수를 초기화합니다.
a=0
b=0
c=0

# 재귀 함수 check를 정의합니다. 이 함수는 주어진 범위 내에서 같은 숫자가 아닌 경우를 찾아내고, 
# 그 경우에는 범위를 9분할하여 다시 검사를 수행합니다.
def check(x,y,n):
    global a,b,c  # 전역 변수를 사용하기 위해 global 키워드를 사용합니다.
    paper=graph[x][y]  # x, y 위치의 숫자를 paper에 저장합니다.
    for i in range(x,x+n):
        for j in range(y,y+n):
            # 만약 paper와 다른 숫자가 발견되면, 
            if paper != graph[i][j]:
                # 9분할하여 재귀적으로 검사를 수행합니다.
                for k in range(3):
                    for l in range(3):
                        check(x+k*n//3,y+l*n//3,n//3)
                # 현재 함수를 종료합니다.
                return
    # 같은 숫자만 존재하면 해당 숫자의 개수를 증가시킵니다.
    if paper == -1:
        a+=1
    elif paper == 0:
        b+=1
    else:
        c+=1

# 초기 범위는 전체 그래프이므로 (0,0)에서 시작하여 크기는 n입니다.
check(0,0,n)

# 각 숫자의 개수를 출력합니다.
print(a)
print(b)
print(c)

🔶 문제 이해하기

예를 들어서 3x3 크기의 2차원 배열을 가지고 있다고 가정해 보겠습니다.

 

graph = [[1, 1, 0], 
         [1, 1, 0], 
         [0, 0, 0]]

 

그리고 check(0, 0, 3)을 호출한다고 하겠습니다. 여기서 (x, y)는 검사를 시작할 위치, n은 검사할 영역의 크기입니다.

처음에는 (0, 0)에서 시작하여 크기 3의 영역, 즉 전체 영역을 검사합니다. paper에는 graph [0][0]인 1이 저장됩니다.

그다음 for 루프를 이용해 (0, 0)부터 (2, 2)까지의 모든 위치를 검사합니다. 이때 graph [0][2]가 paper와 다르므로, 영역을 9 분할하여 다시 검사를 수행합니다.

9 분할은 아래와 같습니다.

 

(0, 0, 1), (0, 1, 1), (0, 2, 1)
(1, 0, 1), (1, 1, 1), (1, 2, 1)
(2, 0, 1), (2, 1, 1), (2, 2, 1)

 

왜 9 분할했을 때 위 값이 나오는지??

 

위의 튜플들 중 (0, 0, 1)은 원래 배열의 (0, 0) 위치에서 시작하여 크기가 1인 영역을 (0, 1, 1)은 (0, 1)에서 시작하여 크기가 1인 영역을 검사하라는 뜻입니다. 

 

다음 튜플 중 (0,2,1)은 배열의 (0,2) 위치에서 시작하여 크기가 1인 영역을 (1,0,1)은 (1,0)에서 시작하여 크기가 1인 영역을 검사하라는 뜻입니다.

 

이런 식으로 9 분할하여 영역을 각각 따로 재귀함수를 통해 조사하게 됩니다.

 

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