[BaekJoon] 백준 1992번 쿼드트리
문제: https://www.acmicpc.net/problem/1992
내코드
문제를 이해하는게 제일 어려웠다. 주어진 설명으로 이해가 가지 않았다.
다른분들이 써놓은 걸로 문제를 이해 했는데, 배열이 주어지면 모두 같은 수 인지 확인하고 맞으면 해당 수를 넣고, 아니면 4등분해서 각각 같은 수 인지 확인하고.. 반복하는 것이다.
간단하게 재귀로 풀었다. 4등분으로 나누고 다시 4등분으로 나누고.. 이렇게 반복하는 과정에서 재귀가 떠올랐다. 다만 재귀로 풀 때에는 조건에 맞게 종료해주는게 중요하다. 특정 조건에 충족했을 때 맞는 값을 반환하는 것이 그나마 제일 까다로웠다.
# BaekJoon 1992.py
def solution(arr, pos, x, y, result):
if pos == 1:
return result + str(arr[y][x])
# 모두 같은지 체크
is_same = True
value = arr[y][x]
for i in range(pos):
for j in range(pos):
if arr[y+i][x+j] != value:
is_same = False
# 같으면
if is_same:
return result + str(arr[y][x])
# 다르면
elif not is_same:
result = result + "("
result = solution(arr, int(pos / 2), x, y, result)
result = solution(arr, int(pos / 2), int(x + (pos / 2)), y, result)
result = solution(arr, int(pos / 2), x, int(y + (pos / 2)), result)
result = solution(arr, int(pos / 2), int(x + (pos / 2)), int(y + (pos / 2)), result)
result = result + ")"
return result
N = int(input())
image = [list(map(int, input())) for _ in range(N)]
r = solution(image, N, 0, 0, "")
print(r)
728x90
반응형
'CS > Algorithm 문제' 카테고리의 다른 글
[BaekJoon] 백준 1927번 최소 힙 (0) | 2021.07.16 |
---|---|
[BaekJoon] 백준 11659번 구간 합 구하기 4 (0) | 2021.07.16 |
[BaekJoon] 백준 1541번 잃어버린 괄호 (0) | 2021.07.13 |
[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙 (0) | 2021.07.07 |
[BaekJoon] 백준 13458번 시험 감독 (0) | 2021.04.22 |