문자열 변환 문제

문제 설명

이 문제는 문자열 A와 B, 그리고 최대 6개의 문자열 변환 규칙을 주고, A를 B로 변환하는 최소 단계 수를 찾는 문제입니다. 각 변환 규칙은 "A1→B1" 형식으로 주어집니다.

예를 들어, A가 "abcd", B가 "xyz"이고 변환 규칙이 다음과 같다면:

• abc→xu
• ud→y
• y→yz

이 경우, A는 3번의 변환을 통해 B로 변환될 수 있습니다.

입력 형식

첫 번째 줄에 두 개의 문자열 A와 B가 주어집니다. 그 다음 줄부터 여러 줄에 걸쳐 변환 규칙들이 주어집니다. 각 줄은 두 개의 문자열 Ai와 Bi로 구성됩니다.

출력 형식

A를 B로 변환하는데 10단계 이내로 가능하다면 최소 단계 수를 출력하고, 그렇지 않으면 NO ANSWER!를 출력합니다.

입력/출력 예시

입력 #1

abcd xyz
abc xu
ud y
y yz

출력 #1

3

무향 그래프 중복 제거 방법 (코드 예시)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
unordered_map<string, bool> visited;
vector<pair<string, string>> rules;

string start, endStr;

void bfs() {
    queue<pair<string, int>> q;
    q.push({start, 0});
    visited[start] = true;

    while (!q.empty()) {
        auto [current, steps] = q.front();
        q.pop();

        if (steps > 10) {
            cout << "NO ANSWER!";
            return;
        }

        if (current == endStr) {
            cout << steps;
            return;
        }

        for (auto &[from, to] : rules) {
            size_t pos = current.find(from);
            while (pos != string::npos) {
                string nextStr = current;
                nextStr.replace(pos, from.size(), to);
                if (!visited[nextStr]) {
                    visited[nextStr] = true;
                    q.push({nextStr, steps + 1});
                }
                nextStr[pos] = '~'; // Avoid infinite loop
                pos = current.find(from, pos + 1);
            }
        }
    }
    cout << "NO ANSWER!";
}

int main() {
    cin >> start >> endStr;
    string a, b;
    while (cin >> a >> b) {
        rules.push_back({a, b});
    }
    bfs();
    return 0;
}

구조체 사용 방법 (코드 예시)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
unordered_map<string, bool> visited;
struct Node {
    string str;
    int step;
};

vector<pair<string, string>> rules;

string start, endStr;

void bfs() {
    queue<Node> q;
    q.push({start, 0});
    visited[start] = true;

    while (!q.empty()) {
        Node curr = q.front();
        q.pop();

        if (curr.step > 10) {
            cout << "NO ANSWER!";
            return;
        }

        if (curr.str == endStr) {
            cout << curr.step;
            return;
        }

        for (auto &[from, to] : rules) {
            string temp = curr.str;
            size_t pos = temp.find(from);
            while (pos != string::npos) {
                string newStr = temp;
                newStr.replace(pos, from.size(), to);
                if (!visited[newStr]) {
                    visited[newStr] = true;
                    q.push({newStr, curr.step + 1});
                }
                temp[pos] = '~'; // Avoid infinite loop
                pos = temp.find(from, pos + 1);
            }
        }
    }
    cout << "NO ANSWER!";
}

int main() {
    cin >> start >> endStr;
    string a, b;
    while (cin >> a >> b) {
        rules.push_back({a, b});
    }
    bfs();
    return 0;
}