알고리즘/백준[baekjoon]
[baekjoon]백준 1992번 : 쿼드트리 (by python 파이썬) 분할,재귀
코딩하는이씨
2022. 5. 22. 17:11
728x90
반응형
https://www.acmicpc.net/problem/1992
1992번: 쿼드트리
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또
www.acmicpc.net
정답 code
#쿼드 트리
n = int(input())
tree = [list(map(int,input())) for _ in range(n)]
def quadtree(x,y,n):
if n == 1:
return str(tree[x][y]) #x: 세로 y: 가로
result = []
for i in range(x, x+n):
for j in range(y, y+n):
if (tree[i][j] != tree[x][y]): #모두 같은수가 아닐시 4등분
result.append('(')
result.extend(quadtree(x, y, n//2)) #왼쪽 위
result.extend(quadtree(x, y+n//2, n//2))# 오른쪽 위
result.extend(quadtree(x+n//2, y ,n//2))#왼쪽 아래
result.extend(quadtree(x + n//2 , y+ n//2 ,n//2))# 오른쪽 아래
result.append(')')
return result
return str(tree[x][y])
print(''.join(quadtree(0, 0, n)))
이번 문제는 전에도 자주 풀었던 유형으로 분할과 재귀를 이용하여 문제를 해결해나가면 된다.
문제가 원하는대로 0과 1이 섞여 있으면 4등분후 계속 탐색한다.
이때 리스트에 append가 아닌 extend로 해야 한다.
처음에 append로 했다가 런타임 오류가 떴다.
https://ooyoung.tistory.com/117
파이썬 append( ), extend( ), insert( ) 함수 차이 / 요소추가함수 비교 (Python)
append( ), extend( ), insert( ) 함수 비교 세 개의 함수 모두 요소를 추가할 수 있는 함수이다. 그런데 추가하는 방식에는 차이가 있다. 그 차이를 아래에서 비교 정리해본다. - 순서 - 1. append( ) 2. extend(.
ooyoung.tistory.com
extend에 대한 설명은 위에 블로그에 잘 설명되어있다.
++
처음엔 분할 재귀문제가 어려웠는데 계속 비슷한 유형을 풀어갈수록 해결법이 잘 떠오르는것 같다.
그래도 아직 약한 분류인 만큼 더 열심히 공부해야겠다.
728x90
반응형