[Python][백준] 1780. 종이의 개수 / 분할정복,재귀 (S2)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

import sys
input = sys.stdin.readline

N = int(input())
lst = [list(map(int,input().split())) for _ in range(N)]
rs = []

def reculsive(x,y,n):
    color = lst[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if color != lst[i][j]:
                for a in range(3):
                    for b in range(3):
                        reculsive(x+(n//3)*a,y+(n//3)*b,n//3)
                return 
        
    if color == -1:
        rs.append(-1)
    elif color == 0 :
        rs.append(0)
    else : 
        rs.append(1)

reculsive(0,0,N)
print(rs.count(-1),rs.count(0),rs.count(1),sep="\n")

 

1. reculsive(재귀) 함수에 color 라는 변수를 선언한다. 

 

2. x,y 좌표에서 각각  만큼 떨어진 만큼 반복문을 수행한다. 

→ 종이가 모두 같은 수로  되어 있는지 확인 

 

3. 만일 변수 color와 lst[i][j]의 값이 다르다면, 리스트를 9등분 해준다.

→ 실제 9등분을 하지는 않고 인덱싱으로 수행

 

4. 재귀함수가 호출되지 않는경우는 종이가 모두 같은 수여서, 재귀함수 아래 쪽의 if문 수행을 할 수 있다.

 

5. rs는 리스트 형태인데,

print 함수에서 *와  sep만 잘 활용하면 반복분 없이 호출 가능하다.

 

코드의 내용을 보면 이게 전부이다
1) 모두 같은 수인지 확인을 위한 2중 반복문 
2) 9등분을 위한 인덱싱 2중 반복문 
3) 값 분리

 

📌  문제 코멘트

개인적으로 좀 어려웠던 문제이다. 

9등분 할 때, 나는 새로운 리스트로 만들어 주어 재귀함수를 호출하려고 했다.

그렇게 하다보니 더 복잡해졌는데, 간단히 인덱싱으로 해결 가능했다.

 

특히, x + (n//3) * a 의 의미 를 살펴보면, 

x는 기본적인 위치를 나타내는 좌표로 생각하면 되고,

(n//3) * 3은 x에서 얼만큼 떨어졌는지를 나타낸다고 보면된다.

 

 

---

📚문제

 

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

 

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 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

예제 출력 1 

10
12
11