[백준 9177] 단어 섞기 (DFS/BFS) (C/C++) (★★)

DFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
string a, b, c;
int T;
bool beforeFlag = true;
bool afterFlag = false;
    
void init()
{
    // 소문자 & 대문자 counting 
    int abCnt[52] = {0};
    int cCnt[52] = {0};
    
    for(int i = 0; i < a.size(); i++)
    {
        if('A' <= a[i] && a[i] <= 'Z')
        {
            abCnt[a[i]-'A'+26]++;
        }
        else
        {
            abCnt[a[i]-'a']++;   
        }
    }    
    
    for(int i = 0; i < b.size(); i++)
    {
        if('A' <= b[i] && b[i] <= 'Z')
        {
            abCnt[b[i]-'A'+26]++;
        }
        else
        {
            abCnt[b[i]-'a']++;    
        }
    }    
    
    for(int i = 0; i < c.size(); i++)
    {
        if('A' <= c[i] && c[i] <= 'Z')
        {
            cCnt[c[i]-'A'+26]++;
        }
        else
        {
            cCnt[c[i]-'a']++;
        }
    }    
    
    for(int i = 0; i < 52; i++)
    {
        if(abCnt[i] != cCnt[i])
        {
            beforeFlag = false;
            return;
        }
    }
}
 
void backtracking(int aIdx, int bIdx, int cIdx, string result)
{
    if(afterFlag == true)
    {
        return;
    }
    
    if(result == c)
    {
        afterFlag = true;
        return;
    }
    
    if(a[aIdx] == c[cIdx] && aIdx < a.size())
    {
        backtracking(aIdx+1, bIdx, cIdx+1, result+a[aIdx]);    
    }
    
    if(b[bIdx] == c[cIdx] && bIdx < b.size())
    {
        backtracking(aIdx, bIdx+1, cIdx+1, result+b[bIdx]);    
    }
} 
 
int main(void)
{
//    freopen("B9177_input.txt", "r", stdin);
    
    cin >> T;
 
    for(int n = 1; n <= T; n++)
    {
        cin >> a >> b >> c;
        
        beforeFlag = true;
        afterFlag = false;
        
        init();
        
        // 소문자 & 대문자 갯수로 미리 판별 
        if(beforeFlag == false)
        {
            printf("Data set %d: no\n", n);
            continue;
        }
        
        backtracking(0, 0, 0, "");
        
        if(afterFlag == true)
        {
            printf("Data set %d: yes\n", n);
        }
        else
        {
            printf("Data set %d: no\n", n);
        }
    }
    
    return 0;
}

 

BFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef struct node
{
    int aIdx;
    int bIdx;
    int cIdx;
}node;
 
string a, b, c;
int T;
bool flag = false;
 
queue<node> q;
int visited[210][210];
 
void init()
{
    for(int i = 0; i < 210; i++)
    {
        for(int j = 0; j < 210; j++)
        {
            visited[i][j] = 0;
        }
    }
}
 
void BFS()
{
    visited[0][0] = 1;
    q.push({0, 0, 0});
    
    while(!q.empty())
    {
        int aIdx = q.front().aIdx;
        int bIdx = q.front().bIdx;
        int cIdx = q.front().cIdx;
        q.pop();
        
        if(cIdx == c.size())
        {
            flag = true;
            return;
        }
        
        if(visited[aIdx+1][bIdx] == 0 && a[aIdx] == c[cIdx])
        {
            visited[aIdx+1][bIdx] = 1;
            q.push({aIdx+1, bIdx, cIdx+1});
        }
        
        if(visited[aIdx][bIdx+1] == 0 && b[bIdx] == c[cIdx])
        {
            visited[aIdx][bIdx+1] = 1;
            q.push({aIdx, bIdx+1, cIdx+1});
        }
    }
} 
 
int main(void)
{
//    freopen("B9177_input.txt", "r", stdin);
    
    cin >> T;
 
    for(int n = 1; n <= T; n++)
    {
        cin >> a >> b >> c;
        
        flag = false;
        
        init();
        
        BFS();
        
        if(flag == true)
        {
            printf("Data set %d: yes\n", n);
        }
        else
        {
            printf("Data set %d: no\n", n);
        }
    }
    
    return 0;
}