티스토리 뷰

https://www.acmicpc.net/problem/19021

트리를 DFS하면서, 노드의 방문을 시작한 시점에 (, 끝내는 시점에 ) 를 붙이는 식으로 올바른 괄호 문자열을 만들어 줄 수 있습니다. 주어진 입력을 트리가 아니라 괄호 문자열이라고 생각하면

  • 1, 2번 연산은 짝이 맞는 괄호 쌍을 추가하는 것이고
  • 3번 연산은 짝이 맞는 괄호 쌍을 제거하는 것

으로 볼 수 있습니다.

Edit Distance와 LCS의 관계처럼, 두 괄호 문자열의 최대 공통 부분 괄호 문자열을 찾아 줍시다. $T_1$ 의 모든 괄호를 제거 / $T_2$ 의 모든 괄호를 추가하는 비용을 미리 지불했다고 하면, 두 괄호 $A, B$ 를 매치했을 때의 비용은 $C_3 \times \text{(A, B를 매칭하는 데 드는 비용)} - C_2 \times \text{(A를 제거하는 비용)} - C_1 \times \text{(B를 추가하는 비용)}$ 입니다. 이 비용 합을 최소화하는 공통 괄호 부분 문자열을 찾으면 됩니다. 여기서 공통 괄호 부분문자열은 일반적인 LCS가 당연히 아고, 두 매치하는 괄호가 LCS에 항상 같이 들어가거나 같이 빠져야 합니다.

$dp_{l_1, r_1, l_2, r_2}$ 를, $S[l_1,r_1)$ 과 $T[l_2, r_2)$ 간의 최소 매칭 합이라고 정의합시다. (이 부분문자열 안에 매칭하지 않는 괄호 쌍이 있을 수 있는데, 이들은 없는 문자 취급합시다). 상태 전이는

  • $S$ 의 앞 문자 제거
  • $T$ 의 앞 문자 제거
  • $S$ 의 앞 문자와 $T$ 의 앞 문자를 매칭: $S = (S_1)S_2, T = (T_1)T_2$ 라고 하면, $(S_1, T_1)$ 의 subproblem과 $(S_2, T_2)$ 의 subproblem이 독립적으로 형성됩니다. 각각에 대해서 문제를 해결한 후 합쳐주면 됩니다.

이렇게 하면 전체 문제가 $O(n^2m^2)$ 에 해결됩니다. 여기까지는 그렇게 어렵지 않고 백준에도 있었던 문제입니다.

아주 기상천외한 아이디어를 사용하여 이를 최적화합니다. 지금 모든 상태 전이는 "맨 앞의 문자 제거", "맨 앞의 매칭하는 괄호 쌍 제거" 와 같이 앞을 기준으로 합니다. 하지만 똑같은 원리를 뒷쪽으로도 적용하면, $S = S_1(S_2), T = T_1(T_2)$ 와 같은 분할을 찾을 수도 있습니다. 만약 $|T_2| < |T_1|$ 이면, 오른쪽을 기준으로 상태 전이를 하고, $|T_1| < |T_2|$ 이면 왼쪽을 기준으로 상태 전이를 합시다. 이 때 다음 정리가 성립합니다.

Theorem. 위와 같이 상태 전이를 했을 때, 유효한 DP 상태에서 등장하는 $(l_2, r_2)$ 쌍은 $O(m \log m)$ 이다.

Proof. (Klein, 1998) 문제의 초기 상태는 1번 정점의 자식으로 이루어진 서브트리이다. 여기에서 할 수 있는 것은, 만약 왼쪽 서브트리가 작다면 왼쪽을 제거하고, 오른쪽 서브트리가 작다면 오른쪽을 제거하는 것이다. 원소를 하나씩 제거하든, 매칭으로 한 서브트리를 한꺼번에 날리든, 서브트리가 제거되는 순서는 똑같다. 고로 어떠한 경우에도 마지막 서브트리는 최후에 제거된다.

즉, ($v$ 번 정점의 자식으로 이루어진 서브트리에서 만드는 서로 다른 쌍) = ($v$의 서브트리 크기) - ($v$ 의 가장 큰 서브트리 크기) + (모든 $v$ 의 자식 $w$ 에 대해, $w$번 정점의 자식으로 이루어진 서브트리에서 만드는 서로 다른 쌍) 과 같이 된다. Heavy-light decomposition의 argument를 사용하여, 1번 정점의 자식으로 이루어진 서브트리에서의 서로 다른 쌍이 $O(m \log m)$ 임을 보일 수 있다. $\blacksquare$

유효한 DP 상태들을 전처리하고 위와 같이 DP를 돌리면 전체 문제가 $O(n^2 m \log m)$ 에 해결됩니다.

여담으로 이 문제의 State-of-the-art 알고리즘은 2007년 Demaine과 Mozes가 발견한 $O(N^3)$ 알고리즘 으로 소개된 알고리즘보다 약간 빠릅니다. Tree Edit Distance는 2017년 APSP로의 Hardness reduction이 발견되었기 때문에, 이보다 빠른 알고리즘은 존재하지 않을 가능성이 높습니다. 하지만 특이 케이스에 대해서는 조금 빠르게 풀 수가 있는데

 

'공부' 카테고리의 다른 글

Constructing a Distance Sensitivity Oracle in O(n^{2.5794}M) Time  (0) 2021.10.10
APIO 2021  (1) 2021.07.29
Klein's Algorithm for Computing Edit Distance on Tree  (0) 2021.07.27
CCO 2019 Shopping Plans  (0) 2021.07.27
2021.07.27 problem solving  (0) 2021.07.27
SCPC 2021 Round 1  (3) 2021.07.17
댓글
댓글쓰기 폼
공지사항
Total
766,127
Today
113
Yesterday
631