소스코드
import sys
input = sys.stdin.readline
N = int(input().strip())
graph = [list(map(int, input().strip().split())) for _ in range(N)]
result = [0,0] # 하얀색, 파란색 색종이 개수
def solve(size, x, y):
global result
# 현재 사이즈에서 정사각형을 만족하는지 확인
standard_color = graph[x][y]
is_same = True
for i in range(x, x + size):
for j in range(y, y + size):
color = graph[i][j]
# 기준 색깔과 다른 경우
if color != standard_color:
is_same = False
break
if not is_same:
break
# 정사각형 사이즈 내에서 모든 색이 동일한 경우
if is_same == True:
result[standard_color] += 1
else:
# 모든 색이 동일하지 않은 경우
half = size // 2
solve(half, x, y) # 1사분면
solve(half, x, y + half) # 2사분면
solve(half, x + half, y) # 3사분면
solve(half, x + half, y + half) # 4사분면
print('\n'.join(map(str, result)))
Python
복사
import sys
input = sys.stdin.readline
N = int(input().strip())
graph = [list(map(int, input().strip().split())) for _ in range(N)]
result = [0,0] # 하얀색, 파란색 색종이 개수
def solve(x,y,size,result):
color = graph[x][y]
# 정사각형 사이즈 내에서 하나라도 색이 맞지 않으면 재귀호출(4분면으로 영역을 나눠서)
for i in range(x, x + size):
for j in range(y, y + size):
if graph[i][j] != color:
half = size // 2
solve(x,y, half, result)
solve(x, y + half, result)
solve(x + half, y, result)
solve(x + half, y + half, result)
return
if color == 0:
result[0] += 1
else:
result[1] += 1
solve(0,0,N,result)
print(f"{result[0]}\n{result[1]}")
Python
복사
풀이
•
전형적인 재귀 문제입니다.
◦
같은 로직이 반복될 것 같이 느껴지는 문제입니다.
•
정사각형 영역의 좌측 상단 첫번째 좌표를 이용해서 기준 색깔을 하나 정하고, 인자로 넘겨준 size 내에서 동일 색이 아닌 사각형이 등장하면 4개의 영역으로 나눠서 재귀호출을 진행합니다.
◦
이때 x,y(정사각형 영역의 첫번째 사각형 좌표), size(정사각형의 크기)를 넘겨줘야 재귀적으로 호출되었을 때도 다시 영역을 분리하거나 색이 동일한지 확인 할 수 있습니다.
•
result 리스트를 만들어서 하얀색과 파란색종이의 개수를 한 변수에서 관리합니다.
복기
•
왜이리 조건을 잘게 잘랐을까?
•
시간 제한을 걸어두고 풀면 자꾸 분기를 많이 쪼개나가는 것 같다.
◦
자꾸 세분화하는 느낌?
◦
쓸데없는 분기가 많다
•
좀 더 여유를 두고 큰 관점에서 바라보고 싶은데 쉽지 않다!
◦
다시 풀어보면서 다음 복기 때는 또 어떻게 풀어내는지 봐야겠다