편집 거리 구하기 문제

편집 거리란?

두 문자열 A, B가 주어질 때, A를 B로 바꾸기 위해 필요한 최소 연산 횟수를 말한다. 대표적인 DP 문제이니 기억해두자.

 

편집에 사용할 수 있는 연산은 아래 3가지 이다.

• 삽입
• 삭제
• 교체

여기서, 문자열 A의 길이를 m, B의 길이를 n 이라 할때, dp[i][j] 는 A의 앞 i개 문자와 B의 앞 j개 문자를 일치시키기 위한 최소 편집 거리를 의미한다.

 

예를 들어, A = "cat", B = "cut" 이라면, 초기 DP 테이블은 아래와 같이 구성할 수 있다.

	""	c	u	t
""	0	1	2	3
c	1
a	2
t	3

 

보통 편집 거리 문제는 작은 문자열에서부터 유도된다. -> 작은 문자열을 A(m), 큰 문자열을 B(n) 으로 잡고 계산하는걸 연습하자.

---

위 상황에서도 A(cat) 를 기준으로 dp[i][j] 를 탐색해보자.

 

위의 세 연산을 점화식으로 표현하면 아래와 같다.

• 삽입 : dp[i][j] = dp[i][j-1] + 1
• 삭제 : dp[i][j] = dp[i-1][j] + 1
• 교체 : dp[i][j] = dp[i-1][j-1]

A를 기준으로 쉽게 말하면,

문자를 삽입 한다는 것은 오른쪽으로 한칸.

문자 삭제는 아래로 한칸.

문자 교체는 대각선 아래로 한칸 을 의미한다.

 

여기서 dp 테이블은 최소 편집 거리를 의미하므로, 그 전의 칸 값을 기준으로 최소값을 선택하여 +1을 해주면 최소 상태를 유지할 수 있다.

 

	""	c	u	t
""	0	1	2	3
c	1	0	1	2
a	2	1	1	2
t	3	2	2	1

 

---

코드

import java.util.Scanner;

public class DP_36 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String A = sc.nextLine();
        String B = sc.nextLine();

        int n = A.length();
        int m = B.length();

        int[][] dp = new int[n+1][m+1];

        for(int i=0; i<=n; i++) {
            dp[i][0] = i;
        }
        for(int i=0; i<=m; i++) {
            dp[0][i] = i;
        }

        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(A.charAt(i-1) == B.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1]));
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}