[BOJ] 3876 sed 이용

문제 요약

문제 링크: 백준 3876 - sed 이용

문제 설명

---

접근 방법

α 를 β로 치환하며 주어진 목표 문자열로 변환시키는 문제다. string을 방문처리하여 가지치기를 하는데 unordered_map을 사용하고, bfs로 최소 치환 횟수를 구해줄 수 있다. 모든 규칙에 대하여 완전탐색을 진행, 치환의 규칙과 문자열 인덱스에 유의해야 한다.

예제 1번에서 a -> bb -> aaaa -> bbbbbbbb 의 형태로 3번에 치환할 수 있다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n;
unordered_map<string, string>m;  // 규칙
unordered_map<string, bool>vis;
string a, b;

void solve() {
    queue<pair<string, int>>q;
    q.push({ a,0 });
    vis[a] = 1;
    int blen = b.length();
    while (q.size()) {
        string s = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if (s == b) {
            cout << cnt << '\n';
            return;
        }
        int slen = s.length();
        if (slen > blen) continue;  // 더 이상 치환에 의미 없음
        for (auto i : m) {
            string f = i.first;
            string k = i.second;
            string ss = s;
            slen = s.length();
            for (int j = 0; j < slen; j++) {
                for (int p = 1; p <= slen - j; p++) {
                    string t = ss.substr(j, p);
                    if (t == f) {
                        ss.erase(j, p);
                        ss.insert(j, k);
                        int dif = k.size();
                        j += dif - 1;
                        slen = ss.length();
                        break;
                    }
                }
            }
            if (vis[ss]) continue;
            vis[ss] = 1;
            q.push({ ss,cnt + 1 });
        }
    }
    cout << -1 << '\n';
}

void input() {
    while (1) {
        cin >> n;
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            string x, y;
            cin >> x >> y;
            m.insert({ x,y });
        }
        cin >> a >> b;
        solve();
        m.clear();
        vis.clear();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
}