[백준] 30375 - Edit distance on table (c++)

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

 

문제 요약

H*W 크기의 격자에 문자들이 주어지고, 문자열 T가 주어진다.
격자의 한 점에서 시작해 상하좌우로 이동하며 나온 경로를 문자열 S로 만들 수 있다.
S와 T의 최소 편집 거리를 구해라.

 

편집 거리는 문자열 A를 문자열 B로 변환하기 위해 필요한 최소 연산 횟수로 정의된다.

• A의 한 문자를 다른 문자로 교체.
• A에 한 문자를 삽입.
• A에서 한 문자를 삭제.

 

풀이 (H*W*S)

• 0-1 BFS

H*W*S개의 정점에서 최단경로를 구하는 문제로 변형시킬 수 있다. 가중치가 1인 동작과 0인 동작을 구분하여 0-1 BFS를 돌릴 수 있다. 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int dx[]{0,0,-1,1},dy[]{-1,1,0,0};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int h,w;cin>>h>>w;
    char c[h][w];
    for(int i=0;i<h;i++) 
        for(int j=0;j<w;j++)
            cin>>c[i][j];
    string t;cin>>t;
    int n=t.size();
    
    int dp[h][w][n+1]{};
    deque<array<int,4>> q;
    for(int x=0;x<h;x++)
        for(int y=0;y<w;y++)
            fill(dp[x][y],dp[x][y]+n+1,1e9),q.push_back({x,y,0,0}),dp[x][y][0]=0;
    while(q.size()) {
        auto [x,y,i,co]=q.front();q.pop_front();
        if(co>dp[x][y][i]) continue;
        if(i==n)
            return cout<<co,0;
        if(dp[x][y][i+1]>co+1&&i<n)
            dp[x][y][i+1]=co+1,q.push_back({x,y,i+1,co+1});
        for(int d=0;d<4;d++) {
            int nx=x+dx[d],ny=y+dy[d];
            if(nx<0||ny<0||nx>=h||ny>=w) continue;
            if(dp[nx][ny][i]>co+1) dp[nx][ny][i]=co+1,q.push_back({nx,ny,i,co+1});
            if(dp[nx][ny][i+1]>co+(c[nx][ny]!=t[i])) {
                dp[nx][ny][i+1]=co+(c[nx][ny]!=t[i]);
                if(c[nx][ny]!=t[i])
                    q.push_back({nx,ny,i+1,co+1});
                else
                    q.push_front({nx,ny,i+1,co});
            }
        }
    }
}