https://www.acmicpc.net/problem/1991
백준 1991번을 풀고 있었다.
트리에서 전위 순회, 중위 순회, 후위 순회를 구현하고 있었는데
변수가 많이 나오다보니 어떤 게 뭘 의미하는 건지 헷갈렸다.
그래서 변수명을 새로 만들어서 지정했더니 디버그하기 더 편해졌다.
예시를 통해 알아보자.
# 후위 순회
def post_order(root_node):
stack = [root_node]
visited = []
while stack:
current = stack[-1]
left_child = tree[current][0]
right_child = tree[current][1]
# 자식 노드의 왼쪽이 있으면 더 탐색
if left_child!='.' and left_child not in visited:
stack.append(left_child)
# 자식 노드의 오른쪽이 있으면 더 탐색 (왼쪽 했으면 오른쪽은 불가능)
elif right_child!='.' and right_child not in visited:
stack.append(right_child)
# 자식 노드가 없으면 pop하고 출력
else:
current = stack.pop()
print(current,end='')
visited.append(current)
# 후위 순회
def post_order(node):
stack = [node]
visited = []
while stack:
current = stack[-1]
# 자식 노드의 왼쪽이 있으면 더 탐색
if tree[current][0]!='.' and tree[current][0] not in visited:
stack.append(tree[current][0])
# 자식 노드의 오른쪽이 있으면 더 탐색 (왼쪽 했으면 오른쪽은 불가능)
elif tree[current][1]!='.' and tree[current][1] not in visited:
stack.append(tree[current][1])
# 자식 노드가 없으면 pop하고 출력
else:
current = stack.pop()
print(current,end='')
visited.append(current)
가장 핵심적인 차이는 크게 2가지다.
node -> root_node
tree[current][0] -> left_child
tree[current][1] -> right_child
def post_order(root_node):
stack = [root_node]
left_child = tree[current][0]
right_child = tree[current][1]
left_child, right_child로 새로 변수를 할당하면
사실 불필요한 메모리를 추가로 쓰는 것이긴하다.
하지만 약간의 메모리를 더 써서 사람이 더 읽기 편한 코드가 되었고
디버그할 떄 더 수월하고 워크플로우를 파악할 수 있었다.