[백준] [Class3] [Silver II] 종이의 개수 - 1780 (파이썬 / Python)

[Silver II] 종이의 개수 - 1780

문제 링크

성능 요약

메모리: 69444 KB, 시간: 4288 ms

분류

분할 정복(divide_and_conquer), 재귀(recursion)

문제 설명

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 3⁷, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

# 풀이1 (Python3 4988ms)

import sys

input = sys.stdin.readline
N = int(input())

graph = [[] * N for i in range(N)]
answer = [0,0,0]
for i in range(N):
    graph[i] = list(map(int,input().split()))

def dfs(x, y, n):
    visited = graph[x][y]

    # 종이 확인
    for i in range(x, x + n):
        for j in range(y, y + n):
            if graph[i][j] != visited:
                # 3 * 3 범위를 재귀적으로 탐색
                for k in range(3):
                    for l in range(3):
                        dfs(x + k * n // 3, y + l * n // 3, n // 3)
                return

    # 카운트
    answer[graph[x][y]] += 1

dfs(0, 0, N)
print(answer[-1])
print(answer[0])
print(answer[1])

# 다른 사람 풀이2 (Phthon3 4288ms)

import sys

# 1. 입력받기 
input = sys.stdin.readline
n = int(input())
paper = []
for i in range(n):
    paper.append(list(map(int,sys.stdin.readline().split())))

# 종이 종류 RESULT 
result = {-1:0, 0:0,1:0}

# 2. 종이의 종류(-1, 0, 1)와 다르면 분할 
def divided(row,col,n):
    curr = paper[row][col] # 종이의 시작 

    for i in range(row, row+n):
        for j in range(col, col+n):
            # 현재 종이 종류와 다르다면 
            if paper[i][j] != curr:
                # 종이 1/3로 분할 (ex. n == 9 , n = 9 -> 3 -> 1 )
                next = n//3
                # 종이를 같은 크기의 종이 9개로 자르므로 
                divided(row, col, next) # 1번째 block (0,0)
                divided(row, col+next, next) # 2번째 block (0,1)
                divided(row, col+(next*2), next) # 3번째 block (0,2)
                divided(row+next, col, next) # 4번째 block (1,0)
                divided(row+next, col+next, next) # 5번째 block (1,1)
                divided(row+next, col+(next*2), next) # 6번째 block (1,2)
                divided(row+(next*2), col, next) # 7번째 block (1,0)
                divided(row+(next*2), col+next, next) # 8번째 block (1,1)
                divided(row+(next*2), col+(next*2), next) # 9번째 block (1,2)
                return 

    # 3. 종이 종류에 따라 count 
    result[curr] +=1 
    return 


divided(0,0,n)

# 4. 결과 return 
for i in result.values():
    print(i)

'''
TIL/회고
- 처음 풀어보는 분할 정복 문제.. 결국 다른 사람의 풀이를 봤다.
- dfs로 풀다가 9개로 다시 쪼개서 푸는 방법이 떠올리기 어려웠다.
- 그리고 return을 제대로 해주지 않아서 머리가 아팠다..
- 분할 정복은 풀이2 방법이 코드는 길어도 빠르고 한눈에 이해가 간다.
'''

풀이

분할정복 (Divide & Conquer) 이란?

• 이름 그대로 작은 문제로 분할해서 문제를 정복하는 것.
• 분할 정복은 DP와 조금의 차이가 있는데 DP는 분할한 문제들이 서로 영향이 미치지만 분할 정복은 서로 영향을 미치지 않는다.
• DP처럼 탑다운 방식과 바텀업 방식이 있다.

분할 정복 알고리즘의 조건

• 문제를 쪼개 나가는 과정에서, 큰 문제와 작은 문제의 구조가 동일하거나 최소한 비슷해야 한다. 즉, 큰 틀에서 봤을 때 큰 문제에서 적용되는 해법이 작은 문제에서 동일하게 적용된다.

• 쪼개진 문제들 간에는 서로 상관관계가 없어야 한다. 즉, 쪼개진 문제들이 풀이 과정에서 서로 영향을 주지 말아야 한다.

• 주어진 조건이 만족하지 않는 경우 주어진 N을 3으로 나눠 9등분으로 재귀함수를 실행한다.
  • 재귀를 실행 시 9등분한 각각의 x,y좌표를 잘 생각해서 넣어준다.
• 그리고 return을 사용해서 분해한 9등분의 함수만 실행되게 한다.
• 출력은 딕셔너리, 리스트 등을 이용한다.

---

Class3은 역시 아직 겪어보지 못한 유형들의 문제가 많다.. 이번 문제는 dfs에서 조금 변형된 문제라 느껴져서 풀만하다고 생각했지만.. 잊고 있던 분할 정복 알고리즘의 문제였다. 분할 정복은 재귀 함수와 궁합이 잘 맞아 분할 정복 알고리즘은 이러한 유형들의 문제가 많다고 한다. 다음에는 이러한 유형 꼭 풀 수 있기를 ..!🙏