트리 편집 거리

시간 제한2초메모리 제한256 MB

요약

잎 삽입과 잎 삭제, 이름 변경 연산으로 순서가 있는 라벨 트리 하나를 다른 하나로 바꾸는 최소 연산 횟수를 구합니다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 트리
정답자: 아직 제출이 없습니다

문제

XML 문서는 계층 구조 데이터를 담기 때문에 보통 순서 있는 라벨 트리로 모델링한다. 트리의 정점 하나는 XML 요소 하나에 대응하고, 정점의 라벨은 그 요소의 태그 이름이다. 간선 하나는 부모 요소와 자식 요소의 관계를 나타낸다. 두 XML 문서가 구조적으로 얼마나 비슷한지 재는 일은 정보 검색에서 자주 다루는 문제다. 여기서는 순서 있는 라벨 트리로 표현한 두 XML 문서의 구조적 유사도를 구한다.

정점이 하나 이상인 루트 트리를 $T$ 라고 하자. 모든 정점에 라벨이 붙어 있으면 $T$ 를 라벨 트리라고 한다. 라벨은 서로 같아도 된다. 모든 정점에서 자식 사이에 왼쪽부터 오른쪽으로 가는 순서가 정해져 있으면 $T$ 를 순서 트리라고 한다.

순서 있는 라벨 트리 $T_1$ 과 $T_2$ 의 유사도는 흔히 트리 편집 거리 $TED(T_1, T_2)$ 로 잰다. $TED(T_1, T_2)$ 는 $T_1$ 을 $T_2$ 로 바꾸는 편집 연산의 최소 횟수다. 트리 $T$ 에 적용할 수 있는 편집 연산은 다음 세 가지다.

$Insert(x)$ : 라벨이 $x$ 인 잎 정점 하나를 넣는다. 연산 전에 부모의 자식이 $d$ 개였다면, 새 정점은 $1 \le i \le d + 1$ 인 어떤 $i$ 에 대해 부모의 $i$ 번째 자식이 된다.
$Delete()$ : 잎 정점 하나를 지운다. 정점이 하나뿐인 트리에는 이 연산을 적용할 수 없다.
$Relabel(x, y)$ : 어떤 정점의 라벨 $x$ 를 라벨 $y$ 로 바꾼다.

연산 한 번이 넣거나 지우거나 라벨을 바꾸는 정점은 정확히 하나다.

그림 1의 두 트리를 보자. $T_1$ 의 잎 정점 C에 $Delete()$ 를 적용하고, 이어서 $Relabel(C, E)$ 와 $Insert(F)$ 를 적용하면 $T_1$ 이 $T_2$ 로 바뀐다. 연산을 두 번 이하로 써서는 $T_1$ 을 $T_2$ 로 바꿀 수 없다. 따라서 $TED(T_1, T_2)$ 는 3이다.

(a) $T_1$ (b) $T_2$

그림 1. 순서 있는 라벨 트리 두 개

주어진 순서 있는 라벨 트리 두 개의 트리 편집 거리를 구하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에 $T_1$ 의 표현이, 둘째 줄에 $T_2$ 의 표현이 주어진다.

트리의 표현 방식은 다음과 같다. 라벨이 $l$ 인 루트 정점 하나로만 이루어진 트리는 $(l)$ 로 적는다. 루트의 라벨이 $l$ 이고 부분 트리가 왼쪽부터 차례로 $S_1, S_2, \ldots, S_d$ 인 트리는 $(l(r_1)(r_2)\cdots(r_d))$ 로 적는다. 여기서 $(r_1), (r_2), \ldots, (r_d)$ 는 각각 $S_1, S_2, \ldots, S_d$ 의 표현이다.

정점의 라벨은 모두 영어 대문자 한 글자다. 표현에는 공백이 없고, 각 트리의 정점 개수는 1 이상 1,000 이하다.

출력

각 테스트 케이스마다 $T_1$ 을 $T_2$ 로 바꾸는 편집 연산의 최소 횟수를 한 줄에 출력한다.

예제3

예제 1

입력

3
(A(B(C)(D))(C(D)))
(A(B(D))(E(D)(F)))
(X(Y(Z(W))))
(W)
(P(P)(P)(P)(P)(P))
(Q(Q)(Q)(Q)(Q))

예상 출력

3
4
6

예제 2

입력

4
(A)
(A)
(A)
(B)
(A(B)(C))
(A(B)(C))
(Z)
(Z(Z))

예상 출력

예제 3

입력

3
(A(B(C)))
(A(C))
(A(B(C(D))))
(A(D))
(A(B(C))(D))
(A(C)(D))

예상 출력

2
3
2