[백준][재귀] 종이의 개수

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

1780번: 종이의 개수

 

내가 작성한 코드

import sys

read = sys.stdin.readline

def read_data():
    N = int(read().rstrip())
    paper = []
    for _ in range(N):
        paper.append(list(map(int, read().rstrip().split())))
    return N, paper

def count(N, i, j, paper):
    tmp = paper[i][j]
    for r in range(i, i+N):
        for c in range(j, j+N):
            if paper[r][c] != tmp:
                return False, 0, 0, 0
    if tmp == -1:
        return True, 1, 0, 0
    if tmp == 0:
        return True, 0, 1, 0
    return True, 0, 0, 1

def recursion(N, i, j, paper):
    done, minus, zero, plus = count(N, i, j, paper)
    if done:
        return minus, zero, plus

    n = N // 3
    for nw_i in range(i, i+N, n):
        for nw_j in range(j, j+N, n):
            m, z, p = recursion(n, nw_i, nw_j, paper)
            minus, zero, plus = minus+m, zero+z, plus+p
    return minus, zero, plus

N, paper = read_data()
for n in recursion(N, 0, 0, paper):
    print(n)

• 재귀
  
  • 현재 모든 값이 동일하면 return
  • 아니면 9등분하여 recursion

 

다른 사람이 작성한 코드

import sys
N = int(sys.stdin.readline())
matrix = []
result = [0] * 3
for _ in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))

def check(start_x: int, start_y: int, n: int):
    temp = matrix[start_x][start_y]
    for i in range(n):
        for j in range(n):
            if temp != matrix[start_x + i][start_y + j]:
                return False
    return True

def divide(start_x: int, start_y: int, n: int):
    if check(start_x, start_y, n):
        result[matrix[start_x][start_y] + 1] += 1
    else:
        for i in range(3):
            for j in range(3):
                divide(start_x + i* n//3, start_y + j* n//3, n//3)
    return

divide(0, 0, N)
for i in range(3):
    print(result[i])

• 위 코드를 참고
  
  • 내 코드랑 똑같아보이는데 이 코드는 통과하는지 확인하기 위해 사용

https://suri78.tistory.com/69

[백준알고리즘] 1780번: 종이의 개수 -Python

기억해야할 것

• Pruning
  
  • 재귀가 발생하면 counting을 처음부터 다시함
  • 따라서, 재귀 조건이 되면 counting을 멈춰야함
• List slicing
  • 리스트 슬라이싱으로 시간초과
  • 인덱스도 헷갈림
• 이 문제로 너무 오래 걸렸음... 재귀 문제를 많이 풀어야 할듯