문제
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
풀이
작은 문제들을 모아서 큰 문제를 해결하는 재귀와 분할정복이 섞인 문제라고 볼 수 있다.
주어진 N이 9라고 했을때 풀어야 할 작은 문제는 9 x 9 전체가 일치하는지 검사해야하고 그 다음으로 3으로 나눈 길이의 작은 조각들이 전부 일치하는지 검사해주면 된다.
따라서 시작 row, col값을 받아서 현재 값을 추출해주고 받아온 길이 N을 활용해 사각형전체를 순회하며 현재값과 일치하는지 검사해준다.
만약 이 현재값과 모든 값이 일치한다면 미리 선언해둔 defalutdict에 1을 더해주고(하나의 종이로 간주하니까) 같지않다면 가로 3등분 세로 3등분을 하면서 재귀함수를 통해서 다시 값을 구해준다.
코드
from collections import defaultdict
import sys
input = sys.stdin.readline
check_cnt = [-1, 0, 1]
N = int(input().rstrip())
count_map = defaultdict(int)
papers = [list(map(int, input().rstrip().split())) for _ in range(N)]
def get_papers(r,c,n):
cur_paper = papers[r][c]
for i in range(r, r+n):
for j in range(c, c+n):
if papers[i][j] != cur_paper:
for partial_row in range(3):
for partial_col in range(3):
nr = r + partial_row * n//3
nc = c + partial_col * n//3
get_papers(nr, nc, n//3)
return
count_map[cur_paper] += 1
get_papers(0, 0, N)
for key in check_cnt:
print(count_map[key])함수화 버전
from collections import defaultdict
import sys
input = sys.stdin.readline
check_cnt = [-1, 0, 1]
N = int(input().rstrip())
count_map = defaultdict(int)
papers = [list(map(int, input().rstrip().split())) for _ in range(N)]
def check_equal_number(r,c,n):
for i in range(r, r+n):
for j in range(c, c+n):
if papers[i][j] != papers[r][c]:
return False
return True
def get_papers(r,c,n):
if check_equal_number(r,c,n):
count_map[papers[r][c]] += 1
return
for partial_row in range(3):
for partial_col in range(3):
get_papers(r + partial_row * n //3 , c + partial_col * n//3, n//3)
get_papers(0, 0, N)
for key in check_cnt:
print(count_map[key])피드백
귀납적 사고도 필요하지만 재귀함수를 생각한대로 구현하는 능력도 중요하다. 오늘 강의를 정리한 이후로 집중이 잘 안 됐지만 그래도 놓치지 않고 끝까지 잘 해냈다.
그리고 다시 원래 하던대로 문제만 '그냥' 풀고있는데 개념 확실히 정리하면서 공부하자.
