Azza's Blog

String A: "Zeil"

String B: "trials"

라고 했을 때, "Zeil" -> "trials" 을 만드는 경우는 다음과 같이 쪼갤 수 있다.

(1. Add Case)

"Zeil" -> "trial" 의 Edit Distance + 1 ( 여기서 +1 은 "s" Add Operation)

(2. Remove Case)

"Zei" -> "trials" 의 Edit Distance + 1 (여기서 +1 은 "l' Remove Operation)

(3. Change Case)

"Zei" -> "trial" 의 Edit Distance + 1 (여기서 +1 은 "l" -> "s" Change Operation)

이 세가지 Case 에서 Recursive 하게 Min 값을 찾아가면 되는 것이다.

물론.. Recursive 하게 풀면 O(3^N) 정도의 복잡도에 깔려 죽겠지..

그래서 DP Table 을 구성하는 데...

DP[n][m] : String A 의 Substring (0,n) 에서 String B 의 Substring (0,m) 로 변환하는 Edit Distance

로 둔다. 그리고 위의 Case 를 참고로 찾아가는 것이다.

위의 풀이에서는 DP Table 에 빈 문자열을 0 번째 인덱스에 채워 계산을 편하게 했다.

그리고 이제 이 Table 을 채워가는 것이다.

How? 윈쪽, 윈쪽 위, 위 쪽의 값을 참고로 채워 나간다.

(1. 윈쪽 참고)

Z -> "" 만드는 Edit Distance + 1 ( +1 은 Add 't' 가 되겠다 )

(2. 위쪽 참고)

"" -> "t" 만드는 Edit Distance + 1 ( +1 은 Remove 'Z' 가 되겠다 )

(3. 왼쪽 위 참고)

"" -> "" 만드는 Edit Distance +1 or 0 (+1 은 Chagne 'Z' -> 't' 가 되겠다. 두 문자가 같으면 0 )

이런식으로 차례대로 채워가면 OK.

소스코드는 아래와 같다.

위 링크에 있는 소스를 사용했지만, 그대로 사용하면 제대로 동작하지 않는다.

마지막 changeDistance 계산식의 마지막 +1 or 0 결정 부분에 괄호를 넣어야 한다.

(Dynamic Programming Solution - 2012/9/11 잘못된 소스 수정)

int editDistance(string x, string y) {
    for(int i = 0; i <= (int)x.length(); i++)
        DP[i][0] = i;
    for(int j = 0; j <= (int)y.length(); j++)
        DP[0][j] = j;

    for(int i = 1; i <= (int)x.length(); i++) {
        for(int j = 1; j <= (int)y.length(); j++) {
            DP[i][j] = min(min(DP[i][j-1]+1, DP[i-1][j]+1), DP[i-1][j-1] + ((x[i-1] == y[j-1]) ? 0 : 1));
        }
    }
    return DP[x.length()][y.length()];
}

(Recusive Solution)

int editDistance (string x, string y) {
    if (x == "")
        return y.length(); // base case
    else if (y == "")
        return x.length(); // base case
    else
    {
        int addDistance = editDistance(x, y.substr(0,y.length()-1)) + 1;
        int removeDistance = editDistance(x.substr(0,x.length()-1), y) + 1;
        int changeDistance = editDistance(x.substr(0,x.length()-1), y.substr(0,y.length()-1))
                            + ((x[x.length()-1] == y[y.length()-1]) ? 0 : 1);

        return min(min(addDistance, removeDistance), changeDistance);
    }
}

이 문제는 여러모로 헷갈렸다.

이제 머리가 잘 안 돌아가나 보다. ㅠㅠ

이 문제의 아이디어의 핵심은 다음이라고 본다.

DP[i][j] : ( 0 <= i < j ), 두 사람이 각각 i, j 번째에서 방문이 끝났을 때, 이동거리 합의 최소값.

이것이 이 문제를 푸는 핵심이다.

이것을 가지고 문제를 쪼개 보면 다음과 같은 경우가 나온다.

DP[i][j] 만들기 전의 상태를 DP[a][b] 라고 했을 때,

1. a -> i 가 되고, b -> j 가 되는 경우. (멀리 간 넘이 다음 도시로 이동한 경우)

2. a -> j 가 되고 b -> i 가 되는 경우. (적게 간 넘이 멀리 간 넘을 넘어 다음 도시로 이동한 경우)

이렇게 두 가지로 나뉜다.

d(i, j) 를 i 번째 도시에서 j 번째 도시까지의 거리라고 할 때,

1번의 경우, DP[i][j] = DP[i][j-1] + d(j-1, j) 로 구할 수 있겠다. (단, i < j-1 )

2번의 경우, DP[i][j] = Min( DP[k][j-1] + d(k, j) ). ( 0 <= k < j-1 )

2번은 i+1 = j 인 경우이다. 이 경우는 멀리있는 넘을 넘어가는 경우의 수를

모두 조사하여 Min 값을 찾는 것이다.

소스는 다음과 같다.

void do_tpt() {
    UINT    min_value, new_value;

    DP[0][1] = 0;
    for(int j = 2; j < NUM_OF_CITIES; j++) {
        for(int i = 0; i <= j-1; i ++) {
            min_value = UINT_MAX;
            if(i < j-1) {   // case 'i' fixed, move 'j-1' to 'j'
                DP[i][j] = DP[i][j-1] + Distance[j-1][j];
            }
            else {    // i == j-1, case 'j-1' fixed..
                min_value = UINT_MAX;
                for(int k = 0; k <= j-2; k++) {
                    new_value = DP[k][j-1] + Distance[k][j];
                    if(new_value < min_value) {
                        min_value = new_value;
                        DP[i][j] = new_value;
                    }
                }
            }
        }
    }
}