백준 1780번 종이의 개수

정보

문제 바로가기 [클릭]

난이도: Silver2

관련 개념: #분할정복 #재귀

---

조건

시간 제한	메모리 제한
2 초	256 MB

---

문제

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

입력

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

출력

10
12
11

---

코드(파이썬)

import sys

def dnq(x, y, k):
    start = paper[x][y]
    
    # 해당 구역이 전부 같은 숫자라면
    if all([all(i==start for i in line[y:y+k]) for line in paper[x:x+k]]):
        result[start] += 1
    # 해당 구역을 더 나눌 수 없다면
    elif k==3:
        
        for key in [paper[x+s_x][y+s_y] for s_x, s_y in sector]:
            result[key] +=1
    # 그 외
    else:
        k //= 3
        for s_x, s_y in sector:
            dnq(x + s_x*k, y + s_y*k, k)
    
n = int(sys.stdin.readline())

paper = [list(map(int, line.split())) for line in sys.stdin.readlines()]
sector = sum([[(sector_x, sector_y) for sector_y in range(3)] for sector_x in range(3)], [])
result = {-1:0, 0:0, 1:0}

dnq(0, 0, n)
print(*result.values(), sep="\n")

---

특이사항

• 내 코드(84,072KB, 4,316ms)에 비해 우수한 코드(바로가기, 68,804KB, 2,852ms)와 비교

  • import sys
    
    def recursion(n, s):
        x, y = s
        standard = paper[x][y]
        temp = {-1 : 0, 0 : 0, 1 : 0}
        flag, t_flag = True, True
            
        for i in range(x, x + n):        
            for j in range(y, y + n):            
                if paper[i][j] != standard:
                    t_flag = False
                    break
            if not t_flag:
                flag = False
                break
                    
        if flag:
            d[standard] += 1
            return
        elif n > 3:
            num = n // 3
            for i in range(3):
                for j in range(3):
                    recursion(num, (x + num * i, y + num * j))
        else:
            for i in range(x, x + n):
                for j in range(y, y + n):            
                    d[paper[i][j]] += 1
            return
                        
                        
    
    input = sys.stdin.readline
    N = int(input())
    paper = [list(map(int, input().rstrip().split())) for _ in range(N)]
    d = {-1 : 0, 0 : 0, 1 : 0}
    
    recursion(N, (0, 0))
    print(d[-1], d[0], d[1], sep = '\n')
    

  • 다음 구역 선택 시
    • 기존: sector 리스트 생성해서 사용
    • 개선: 이중 반복문으로 사용
  • 구역이 한 가지 색으로만 이루어져있는지 확인 방법
    • 기존: all 함수 사용
    • 개선: 각 위치를 확인하고 만약 t_flag 값이 False로 바뀌면 여러 색이 있다고 판단

---

참고문헌

-