백준 9177번: 단어 섞기 (C++)

접근

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

9177번: 단어 섞기

처음엔 당연히 1번, 2번, 3번 문자열의 인덱스를 i, j, k로 두고 string[1][i]와 string[3][k]가 일치한다면 i 와 k 를 1씩 늘려주면 그냥 풀리는 문제라고 생각했는데, string[1][i] 와 string[2][j], string[3][k]가 동시에 일치하는 경우를 모두 탐색해야 하기 때문에 두개 모두 탐색하기 위하여 bfs를 이용하게 되었다.

bfs 알고리즘을 이용하면서 큐에 {i, j, k} 를 추가하면서 string[1][i]와 string[3][k]가 일치한다면 {i + 1, j, k + 1} 을 큐에 추가해주고 반대로 string[2][j]와 string[3][k]가 일치한다면 {i, j + 1, k + 1} 를 큐에 추가, 그리고 string[1][i] 와 string[2][j], string[3][k]가 모두 일치한다면 두 가지 모두 추가하여 모든 경우를 빠짐 없이 탐색해 줄 수 있다. 그리고 그렇게 분화될 때 같은 경우를 중복 탐색하지 않기 위하여 visited[i][j] 배열을 이용해주었다.

코드

#include <cstring>
#include <iostream>
#include <queue>
#include <string>

using namespace std;

#define endl '\n'
#define MAX_L 201

struct info {
    int first;
    int second;
    int third;
};

int N;
string Data[3];
int visited[MAX_L][MAX_L];

int bfs() {
    memset(visited, 0, sizeof(visited));
    queue<info> Q;
    Q.push({0, 0, 0});
    visited[0][0] = 1;
    while (!Q.empty()) {
        int first = Q.front().first;
        int second = Q.front().second;
        int third = Q.front().third;
        Q.pop();
        if (third == Data[2].length()) return 1;
        // third 인덱스에 해당하는 문자가 first 인덱스 문자, second 인덱스 문자와 동시에 일치할 경우 두가지 모두 큐에 넣어 탐색해준다.
        if (first < Data[0].length() && Data[0][first] == Data[2][third] && visited[first + 1][second] == 0) {
            Q.push({first + 1, second, third + 1});
            visited[first + 1][second] = 1;
        }
        if (second < Data[1].length() && Data[1][second] == Data[2][third] && visited[first][second + 1] == 0) {
            Q.push({first, second + 1, third + 1});
            visited[first][second + 1] = 1;
        }
    }
    return 0;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> Data[0] >> Data[1] >> Data[2];
        string ans;
        if (bfs()) {
            ans = "yes";
        } else {
            ans = "no";
        }
        cout << "Data set " << i << ": " << ans << endl;
    }

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!