문제 바로가기
문제:
두 바이너리 트리 A와 B는 다음과 같은 두 조건을 만족할 때 동등하다고 한다. 1. 두 트리가 비어있다. 또는, 2. 두 트리의 루트가 같다. 또: (a) A의 왼쪽 서브 트리가 B의 왼쪽 서브 트리와 동등하고, A의 오른쪽 서브 트리가 B의 오른쪽 서브 트리와 동등하다. 또는, (b) A의 왼쪽 서브 트리가 B의 오른쪽 서브 트리와 동등하고, A의 오른쪽 서브 트리가 B의 왼쪽 서브 트리와 동등하다. 예를 들어, 아래 왼쪽 3개 트리는 서로 동등하다. 하지만, 가장 오른쪽 트리와는 동등하지 않다.
두 바이너리 트리가 주어졌을 때, 동등한지 아닌지 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 각 줄은 비교해야 하는 트리의 정보이다. 각 트리의 정보는 포스트오더로 주어진다. 서브트리가 없는 경우에는 nil로 주어진다. 트리의 모든 데이터는 알파벳 대문자이다. 각 줄의 마지막은 end가 있다. 예를 들어, 문제 설명의 가장 왼쪽 그림을 포스트오더로 나타내면 다음과 같다. nil nil nil G F nil nil C nil nil E nil D B A end
출력:
각 테스트 케이스에 대해서, 두 트리가 동등하면 true를, 아니면 false를 출력한다.
풀이 :
굉장히 푸는데 시간이 오래 걸렸던 문제였다.
트리구조가 어려웠고 일단 포스트 오더 용어 를 몰랐기 때문에 어떻게 내려오는지 몰랐다.
포스터 오더는 후위탐색인데 왼쪽 노드 자식부터 탐색하는 것이다.
즉 자식 두개가 스택에 차게 되면 그 다음에 나오는 노드는 부모가 된다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
def postorder(graph, tree):
stk = []
for i in graph:
if i == "nil":
i = 0
else:
i = ord(i) - ord("A") + 1
if i != 0 and len(stk) >= 2:
right = stk.pop()
left = stk.pop()
tree[right] = i
tree[left] = i
stk.append(i)
root = stk[-1]
tree[root] = root
return tree
for _ in range(n):
# end 제거
A = list(map(str, sys.stdin.readline().rstrip().split()))[:-1]
B = list(map(str, sys.stdin.readline().rstrip().split()))[:-1]
AA = [0] * 27
BB = [0] * 27
if len(A) in [1, 2] and len(B) in [1, 2]:
print("true")
continue
elif len(A) != len(B):
print("false")
continue
left = postorder(A, AA)
right = postorder(B, BB)
res = True
for left_num, right_num in zip(left[1::], right[1::]):
if left_num != right_num:
res = False
break
print("true" if res else "false")
나는 스택을 사용해서 풀었다.
알파벳들이 들어오기 때문에 쉽게 하기 위해서 각 알파벳을 숫자로 변환하였다.
스택에 노드들을 넣어주는데. nil 일 경우에는 0 으로 변환해서 넣어주고.
넣다가 스택에 길이가 2 이상이고, 현재 들어가려는 노드가 0이 아니면
지금 스택에 있는 노드가 좌 우 노드가 된다.
댓글