BOJ 11503 Tree Edit

 

문제 링크 : https://www.acmicpc.net/problem/11503

11503번: Tree Edit

 

문제가 길어서 대충 읽었다가 'ordered tree' 라는 조건을 놓쳐서 시간을 많이 허비했다.

자식들의 순서가 강제되는지 여부에 따라 전혀 다른 문제가 된다.

 

한 노드의 자식 노드가 A B 로 주어진 것을 B A 로 바꾸어야 하는 경우를 생각해보자.

본 문제에서와 같이 자식들의 순서가 강제되는 경우는 '편집 거리' 문제이다.

 

하지만 자식들의 순서가 없다면,

요리조리 짝을 지어야하므로 플로우를 만들어 최솟값을 구하는 MCMF 로 문제를 풀거나,

짝지어진 부분집합을 고려하는 복잡한 dp 문제가 된다.

 

문제의 해결은 두 가지를 결합하면 된다.

1. 주어진 문자열에서 2 개의 tree 구조를 만드는 것. 

2. 두 개의 tree 의 root 를 시작으로 재귀적으로 자식 노드들 사이의 편집 거리를 구한다.

 

dp[i][j] 는 첫 트리의 i 번째 자식까지를 두 번째 트리의 j 번째 자식까지와 일치시키는데 필요한 비용이다.

평범한 편집 거리 문제와 차이가 없다.

 

(1) dp[i-1][j] 에서 dp[i][j] 로의 이행은 첫 트리의 i 번째 자식(서브트리)의 제거.

(2) dp[i][j-1] 에서의 이행은 두 번째 트리의 j 번째 자식을 첫 트리에 추가.

(3) dp[i-1][j-1] 에서의 이행은 첫 트리의 i 번째 자식을 두 번째 트리의 j 번째 자식으로 변경. 

 

#include<bits/stdc++.h>

using namespace std;

struct tree{
    char tag;
    int sz;
    tree() {}
    ~tree(){
        for(int i=0;i<children.size();i++)
            delete children[i];
    }
    vector<tree*> children;
} *rt1, *rt2;

int p; char str[3001];

tree *make_tree(){
    tree *tmp=new tree();
    tmp->tag=str[++p];
    tmp->sz=0;
    while(str[++p]=='('){
        tmp->children.push_back(make_tree());
        tmp->sz+=tmp->children.back()->sz;
    }
    tmp->sz+=1;
    return tmp;
}

int edit(tree *r1, tree *r2){
    int sz1=r1->children.size(), sz2=r2->children.size();
    vector<vector<int>> dp(sz1+1, vector<int>(sz2+1));
    
    for(int i=1;i<=sz1;i++)
        dp[i][0]=dp[i-1][0]+r1->children[i-1]->sz;
    for(int i=1;i<=sz2;i++)
        dp[0][i]=dp[0][i-1]+r2->children[i-1]->sz;
    for(int i=1;i<=sz1;i++){
        for(int j=1;j<=sz2;j++){
            dp[i][j]=min(min(dp[i-1][j]+r1->children[i-1]->sz,
                             dp[i][j-1]+r2->children[j-1]->sz),
              dp[i-1][j-1]+edit(r1->children[i-1], r2->children[j-1]));
                        
        }
    }
    return dp[sz1][sz2]+(r1->tag != r2->tag);
}

void solve(){
    p=0;
    scanf("%s",str);
    rt1=make_tree();
    
    p=0;
    scanf("%s",str);
    rt2=make_tree();
    
    printf("%d\n", edit(rt1,rt2));
    delete rt1, delete rt2;
}

int main(){
    int T; scanf("%d",&T);
    while(T--)
        solve();   
}