백준(BOJ) 20542 받아쓰기 C++ 풀이

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

20542번: 받아쓰기

문제 풀이에 사용된 알고리즘: DP, 편집 거리, Levenshtein Distance

 

(정답 문자열)과 (내가 답안으로 작성한 문자열)이 같아지도록 얼마나 수정(편집, edit)을 진행해야를 수치화하는 문제이다.

 

Levenshtein Distance, 편집거리라고 하는 알고리즘을 적용해서 쉽게 풀 수 있는 문제이다.

 

동적 프로그래밍(DP)로 구현할 수 있다.

 

편집 거리에 대한 이론적인 내용은 다음의 블로그에서 참조하였다.

https://madplay.github.io/post/levenshtein-distance-edit-distance

편집거리 알고리즘 Levenshtein Distance(Edit Distance Algorithm)

 

이 문제를 풀 때 몇가지 유의할 점은 다음과 같다.

 

수정 중 변환 비용은 두 문자가 동일한지 아닌지에 의해 결정되는데,  답안의 i는 정답의 i, j, l과 동일한 문자로 취급하고, 답안의 v는 정답의 v, w와 동일한 문자로 취급한다는 점이다.

 

이런 이유로 char a와 char b가 있을 때 단순히 ==으로 비교를 진행하지 않고, 별도의 함수를 구현하였다.

 

그리고 정답과 답안의 길이인 m과 n이 1~100만의 범위를 갖는데, dp 배열을 만들기 위해서 d[1000000][1000000]을 선언하면 용량 초과가 발생한다.

 

하지만 n * m은 1천만을 넘지 않는다는 조건이 있으므로, dp 배열을 동적으로 생성할 수 있다면 크게 문제가 되지 않음을 알 수 있다.

 

그렇다고 어려운 동적할당으로 배열을 선언하는 것보다는 vector와 resize를 이용해서 구현하였다.

 

/* BOJ 20542 받아쓰기 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n, m;
string source, target;
vector<vector<int>> dp;
 
bool is_equal(char source_c, char target_c)
{
    if (source_c == 'i')
    {
        if (target_c == 'i' || target_c == 'j' || target_c == 'l')
            return true;
        else return false;
    }
    else if (source_c == 'v')
    {
        if (target_c == 'v' || target_c == 'w')
            return true;
        else
            return false;
    }
    else
        return source_c == target_c;
}
 
int levenshtein_distance(string source, string target)
{
    for (int i = 0; i < target.length(); i++)
    {
        for (int j = 0; j < source.length(); j++)
        {
            if (i == 0)
                dp[i][j] = j;
            else if (j == 0)
                dp[i][j] = i;
            else
            {
                int replace_cost = 0;
                if (!is_equal(source[j], target[i]))
                    replace_cost = 1;
 
                dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + replace_cost));
            }
        }
    }
    return dp[m][n];
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
    cin >> source >> target;
 
    source = " " + source, target = " " + target;
 
    dp.resize(m + 1);
    for (int i = 0; i < m + 1; i++)
        dp[i].resize(n + 1);
 
    cout << levenshtein_distance(source, target) << endl;
 
    return 0;
}