트리 - 구간트리 문제1 족보 탐험

이한울·2019년 7월 16일
0

트리

목록 보기
8/10

문제 파악

트리의 최소 공통 조상을 구해서 트리의 노드에서 노드까지 가는 거리를 구하는 문제이다. 직관적인 방식을 떠올리면 시간 복잡도가 너무 커지게 되고, 트립을 쓰게 되면 구현이 어렵고 구간 트리를 활용한 문제 취지를 벗어나는 것 같아서 구간 트리를 사용하는 방법을 떠올려 보려고 했지만 떠오르지 않았다.

문제 풀이

구간 트리 활용

구간 트리를 활용하여 이 문제를 푸는 방법은, 트리의 최소 공통 조상이 트리 상의 두 노드의 경로에서 가장 최상위에 있는 노드라는 것이다. 최상위에 있는 노드라는 것은 트리를 전위 순회 했을 때 가장 먼저 발견하는 노드라는 뜻이다. 따라서 노드들을 전위순회 했을 때 발견하는 순서들을 컨테이너에 저장해 두고, 최소 공통 조상을 구하고 싶은 두 노드의 위치에 대해 RMQ 질의를 하게 되면 최소값을 구해주게 되는데, 이 최소값이 최상위 노드가 된다.

인덱스를 위한 컨테이너

원래 문제에서의 노드 번호는, 트리가 전위 순회하면서 방문하는 순서와는 다르므로 이를 위한 일련 번호를 만들어 줘야 하고 두 번호 사이의 호환을 위한 작업도 필요하다.
이를 위해 no2serial, serial2no라는 벡터를 사용하는데, 각 번호를 인덱스로 사용하여 다른 번호의 값을 구할 수 있다. 트리를 전위 순회 하면서 두 컨테이너를 만들어 준다. 이 때 트리의 부모 노드가 자식 노드를 방문하고 현재 노드로 다시 돌아온 것에 대한 처리를 해줘야 해당 노드가 처음 발견했을 때 뿐만 아니라 다음 자식들에 대하여도 최상위 노드로 인식될 수 있다.

느낀점

두가지 다른 특성을 가진 인덱스의 호환을 위한 컨테이너 활용.
구간 트리를 단순히 숫자가 가장 작은 값을 리턴한다는 개념에서 확장해 숫자에 방문 순서와 같은 특성을 부여하면 다양하게 활용될 수 있다.

profile
Backend Engineer 이한울입니다

0개의 댓글