[백준][python] 1780번: 종이의 개수
1780번: 종이의 개수
문제
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다.
우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
- 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
- (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
입력 조건
첫째 줄에 N(1 ≤ N ≤ $3^7$, N은 $3^k$ 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.
출력 조건
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.
첫 번째 시도 .
# 종이의 크기를 받음.
n = int(input())
paper = [list(map(int,input().split())) for i in range(n)]
result=[]
#종이의 가장 앞쪽의 한칸과 나머지 칸들의 색들을 비교하여 하나라도 안맞다면
#9등분 후 재귀를 통하여 색을 다시 검사함.
def cut(x,y,n):
#좌측 위 모서리 값을 기준으로 비교
color = paper[x][y]
for i in range(x,x+n):
for j in range(y,y+n):
#만약 색상이 다른 것이 하나라도 있다면 ? 분할하고 다시 시행.(재귀)
if color != paper[i][j]:
cut(x,y,n//3)
cut(x+n//3,y,n//3)
cut(x+(2*(n//3)),y,n//3)
cut(x,y+(n//3),n//3)
cut(x+(n//3),y+(n//3),n//3)
cut(x+(2*(n//3)),y+(n//3),n//3)
cut(x,y+(2*(n//3)),n//3)
cut(x+(n//3),y+(2*(n//3)),n//3)
cut(x+(2*(n//3)),y+(2*(n//3)),n//3)
return
#더 이상 일치하지 않는 컬러가 없다면 그 색상을 result리스트에 더해줌.
result.append(color)
cut(0,0,n)
print(result.count(-1))
print(result.count(0))
print(result.count(1))
»intput
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
»output
10
12
11
success
🌝 Thinking
위 색종이 만들기는 4등분하여 재귀를 이용한 분할정복,
이 문제는 9등분을 할 뿐 전체적인 로직은 일치한다.
-
색종의 전체의 색상이 일치하지 않으면 9등분을 함. 이 와 같은 과정을 계속 반복한다.
✔ 재귀함수를 이용하면 쉽게 구현이 가능하겠구나!
-
자른 색종이에서 한부분이라도 색상이 일치하지 않으면 9등분 해야 한다.
✔ 기준을 잡고, 기준색과 일치하지 않는 색상이 있으면 바로 재귀함수를 통해 위의 과정 반복.
-
만약 모든 색상이 일치한다면 ?
✔ 재귀호출 아래에 기준색을 저장한다.
💡 깨달은 점.
-
재귀함수를 구현 할때 재귀에서 빠져나온 후(원하는 시행이 끝났을 때), 과정은 재귀 호출을 한 문장 밑에다 코딩을 하면 되는구나!
(재귀함수 쉬운듯하면서도 로직이 꽤나 복잡하다.)
댓글남기기