문제 링크
https://www.acmicpc.net/problem/1780
문제 유형
분할정복
🌈 문제
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.
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로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.
10
12
11💡 아이디어
먼저 이 문제를 BFS로 접근해서 풀려고 했다.
visited 2차원 배열을 하나 더 만들고 방문한 곳을 제외하면서 모든 2차원 배열을 검사한다. 배열에는 3의 7제곱, 약 2100 * 2100 = 4,410,000 이므로 2차원 배열을 모두 검사해도 시간 안에는 모든 값을 계산할 수 있다.
하지만 이 문제는 이미 입력부터 문제의 의도가 다분히 드러난다. 3의 n제곱 꼴로 배열을 입력받으므로 3 단위로 이차원 배열을 짤라먹어 작은 단위로 나눈 다음에 코드를 검사해야 한다
👨💻 코드 작성
N = int(input())
count = 0
answer0 = 0
answer1 = 0
answern1 = 0
lst=[]
alst=[]
for _ in range(N):
alst = list(map(int, input().split()))
lst.append(alst)
print(lst)
count = N // 3
def checknum(x1, y1, x2, y2):
global answer0
global answer1
global answern1
cnt = 0
list1 =[]
for i in range(x1, x2 + 1):
for j in range(y1, y2 + 1):
list1.append(lst[i][j])
num = list1[0]
for i in range(1, 9):
if num == list1[i]:
cnt = cnt + 1
if cnt == 8:
if num == 1:
answer1 = answer1 + 1
elif num == -1:
answern1 = answern1 + 1
else:
answer0 = answer0 + 1
else:
for i in range(9):
if list1[i] == 1:
answer1 = answer1 + 1
elif list1[i] == -1:
answern1 = answern1 + 1
else:
answer0 = answer0 + 1
for i in range(count):
for j in range(count):
j = j * 3
checknum(i * 3, j, i * 3 + 2, j + 2)
print(answern1)
print(answer0)
print(answer1)받은 배열을 모든 3 x 3배열로 쪼개서 9번만큼의 루프를 돌면서 각 숫자 요소들을 체크한다. 다른 예제들은 모두 통과하나, 아래 예제를 통과하지 못한다.
9
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1이 때 1에 대한 것만 1이 출력되어야 하는데, 1이 9번 나온 걸로 출력된다.
그래서 아래와 같이 코드를 고쳤다.
N = int(input())
count = 0
answer0 = 0
answer1 = 0
answern1 = 0
lst=[]
alst=[]
for _ in range(N):
alst = list(map(int, input().split()))
lst.append(alst)
count = N // 3
def checknum(x1, y1, x2, y2):
global answer0
global answer1
global answern1
cnt = 0
list1 =[]
for i in range(x1, x2 + 1):
for j in range(y1, y2 + 1):
list1.append(lst[i][j])
num = list1[0]
for i in range(1, 9):
if num == list1[i]:
cnt = cnt + 1
if cnt == 8:
if num == 1:
answer1 = answer1 + 1
elif num == -1:
answern1 = answern1 + 1
else:
answer0 = answer0 + 1
else:
for i in range(9):
if list1[i] == 1:
answer1 = answer1 + 1
elif list1[i] == -1:
answern1 = answern1 + 1
else:
answer0 = answer0 + 1
for i in range(count):
for j in range(count):
j = j * 3
checknum(i * 3, j, i * 3 + 2, j + 2)
if answer1 == 0 and answer0 == 0:
print(1) #-1
print(0) # 0
print(0) # 1
elif answer0 == 0 and answern1 == 0:
print(0) #-1
print(0) # 0
print(1) # 1
elif answer1 == 0 and answern1 == 0:
print(0) #-1
print(1) # 0
print(0) # 1
else:
print(answern1)
print(answer0)
print(answer1)이렇게 하면 정답은 맞으나..
코드가 예쁘다고는 할 수 없겠다.
다른 분들은 어떻게 풀었는지 한번 확인해보자. 많은 사람들이 분할 정복이기 때문에 재귀함수를 이용한 것을 확인할 수 있었다. 여기서 재귀함수를 이용하는 원리는 9개로 쪼개는 작업을 재귀함수로 진행하여 왼쪽 위의 좌표, 그리고 숫자를 체크해주는 것이다.
쪼개진 종이들 단위로 체크하는데, 색이 달라질 때와 달라지지 않을때를 나누어 계산하기 때문에 한번에 처리할 수 있는 코드도 작성될 수 있는 것이다.
만약 같지 않은 코드가 등장한다면 곧바로 3*3 단위로 주변을 살펴본(?)뒤에, result에 값을 더하고 만약 모든 것이 같다면 첫 숫자로 그 결과를 내주는 것이다.
N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]
result_minus = 0
result_zero = 0
result_plus = 0
def dfs(x, y, n):
global result_plus, result_zero, result_minus
num_check = lst[x][y]
for i in range(x, x + n):
for j in range(y, y + n):
if lst[i][j] != num_check: #숫자가 일치하지 않는다면
for k in range(3):
for l in range(3):
dfs(x + k * n //3, y + l * n //3, n // 3)
return
if num_check == -1:
result_minus += 1
elif num_check == 0:
result_zero += 1
else:
result_plus += 1
dfs(0, 0, N)
print(result_minus)
print(result_zero)
print(result_plus)