[백준 파이썬] 1780 종이의 개수

📌문제 출처

백준 단계별 문제풀이 - 분할 정복
https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

❓ 문제

❗ 풀이

• dfs, 분할정복 알고리즘 사용

📗 풀이 코드

import sys
input = sys.stdin.readline

def dac(paper,len_set,n):
    if len_set == 1: # 종이의 원소 집합 길이가 1이라면
        ans[paper[0][0]] += 1
    else : # 그렇지 않다면 분할진행
        for i in range(0,n,n//3): # n=9일때, i=0,3,6
            for j in range(0,n,n//3): # n=9일때, j=0,3,6
                div_paper = [] # 한 구분면
                set_div_paper = set() # 한 구분면의 원소 집합
                for k in range(n//3): # n=9일때, k=0,1,2
                    row = paper[i+k][j:j+n//3] # 한 구분면의 한 행
                    div_paper.append(row)
                    set_div_paper = set_div_paper.union(set(row)) # 원소 집합 추가
                dac(div_paper,len(set_div_paper),n//3)
                
n = int(input())
paper = []
set_paper = set() # 종이의 원소만 중복없이 담아줄 set
for _ in range(n):
    row = list(map(int,input().split()))
    set_paper = set_paper.union(set(row)) # set 합집합 연산
    paper.append(row)
ans = {-1:0,0:0,1:0} # ans dictionary화
dac(paper,len(set_paper),n)
for i in [-1,0,1]:
    print(ans[i])

📗 코드 해설

• 분할정복 방식으로 구분면을 만들며 dfs를 해내간다.
• 모든 원소가 똑같은지 확인하기 위해서 합집합 연산을 활용한다.
• 맨 처음 입력값과 입력값의 원소 개수, n을 넣고 분할정복을 시작한다.
• 한번 분할정복을 시작하면 먼저 원소의 개수가 한개인지 확인하고, 한개라면(모두 같다면) 정답 종이개수를 늘려준다.
• 모두 같지 않다면 구분할을 진행한다. 구분할은 각 구분면 마다 왼쪽 위의 꼭지점을 i,j에 담아두고,
  꼭지점부터 시작하여 (i,j) ~ (i+n//3,j+n//3)을 담아준다.
• 이때 각 행마다 set으로 만들어 원소 개수를 세줄 수 있다.
• 추가로 dfs가 진행될 때에는 구분면과, 원소 개수, 구분면의 길이(n//3)을 넣고 진행한다.