[백준] 1780번 종이의 개수 - (Python)

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

1780번: 종이의 개수

문제의 형태를 보니, 전형적인 분할정복 문제입니다. 단순히 재귀로 구현하게 되면 메모리초과나 시간초과가 발생하니, 경우를 나누어서 접근하는 것이 중요합니다. 2630번 색종이 만들기와 사실상 동일한 문제라고 봐도 무방합니다. 같은 값을 가졌는지 판별 후, Divide and Conquer을 실행합니다. 함수가 종료되면, 횟수를 카운팅 하면 됩니다.

※ 고려사항

1. 입출력 형식

2. 분할정복 함수

---

1. 입출력 형식

입력의 경우 2차원 행렬로 값을 입력받고 있습니다. 그래프 문제를 많이 풀어보셨다면, 해당 입력처리는 굉장히 간단할 것입니다. 컴프리헨션을 통해 list로 값을 split 하여 받으면 됩니다. 추가적인 설명은 제 게시물의 그래프 문제를 참고해 주세요!

https://yunway.tistory.com/10

[백준] 11403번 경로 찾기 - (Python)

해당 코드는 다음과 같습니다.

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)
n = int(input())

# 행렬
matrix = [list(map(int, input().split())) for _ in range(n)]

# 종이 개수
cnt = []

 

2. 분할정복 함수

이 문제의 핵심 부분입니다. 앞서 언급했듯이, 2630번 문제를 풀어보셨다면 동일한 문제라는 느낌이 많이 들것입니다. 해당 함수에서 받은 x, y값을 matrix에 대입한 값을 모든 matrix와 비교합니다. 그러는 과정에서 값이 1개라도 다른 게 발생한다면, 분할정복을 시행합니다. 9개의 구간으로 나눠지기 때문에 입력크기 N은 3으로 나눈 몫으로 줄어들고, 각 좌표는 이 N값을 적절하게 더해서 만듭니다. 

규칙을 조금 더 자세히 설명해 드리면, N이 9일 때, (0, 0), (0, 3), (0, 6), (3, 0), (3, 3), (3, 6), (6, 0), (6, 3), (6, 6)으로 분할됩니다. 즉, N을 3으로 나눈 몫을 x, y좌표에 (0, 1, 2)를 곱해준 값을 더해주면 됩니다.

코드를 통해 쉽게 이해해 봅시다.

# 분할정복
def divide(x, y, n):
    color = matrix[x][y]

    # 색 같은지 판별
    for i in range(x, x + n):
        for j in range(y, y + n):

            # 색깔이 다르면 분할정복
            if color != matrix[i][j]:
                for a in range(3):
                    for b in range(3):
                        divide(x + (n//3)*a, y + (n//3)*b, n//3)
                return

    # 색깔에 따라 개수 삽입
    if color == 1:
        cnt.append(1)

    elif color == -1:
        cnt.append(-1)

    else:
        cnt.append(0)

---

전체코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)
n = int(input())

# 행렬
matrix = [list(map(int, input().split())) for _ in range(n)]

# 종이 개수
cnt = []

# 분할정복
def divide(x, y, n):
    color = matrix[x][y]

    # 색 같은지 판별
    for i in range(x, x + n):
        for j in range(y, y + n):

            # 색깔이 다르면 분할정복
            if color != matrix[i][j]:
                for a in range(3):
                    for b in range(3):
                        divide(x + (n//3)*a, y + (n//3)*b, n//3)
                return

    # 색깔에 따라 개수 삽입
    if color == 1:
        cnt.append(1)

    elif color == -1:
        cnt.append(-1)

    else:
        cnt.append(0)

divide(0, 0, n)
print(cnt.count(-1), cnt.count(0), cnt.count(1), sep='\n')

 

---

확실히 분할정복 문제도, 처음 접했을 때는 시간초과 늪에서 벗어나지 못했으나 많은 학습을 통해 익숙해지고 있습니다. 모든 자료구조도 반복만이 살길임을 느끼고 있습니다. '노력은 절대 배신하지 않는다' 제가 마음에 새기는 키워드인데, 역시 배신하지 않은 듯합니다 ㅎㅎ

설명의 오류나, 궁금하신 점은 언제든 피드백해주시면 감사하겠습니다 ^~^