[9177번] 단어 섞기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS :: http://www.crocus.co.kr/521

이 문제를 보면서 많은 것을 느낀 것 같다.

한줄의 코딩 차이로 메모리 초과를 받느냐 AC를 받느냐를 결정한다는게 너무 신기했고, 결국 알고리즘 하나 차이로 프로그램의 흥망성쇠가 결정된다는 것을 이 문제를 통해 다시 느낀 것 같다.

6번의 메모리 초과를 받은 후 이 문제가 너무 궁금하여 출처를 찾아 검색을 해보았고, 결국 이 문제를 푸는 법을 보았다.

나는 문제를 풀 때, 다음 단어가 어떻게 오는지 queue에 담아 BFS를 돌렸지만, AC코드는 현재 단어가 어떻게 되는지를 queue에 담아 BFS를 돌리고 있었다.

이 두 과정 차이로 문제의 정답 / 오답 차이가 갈렸다.

두가지 코드를 올리려 한다.

첫번째 코드는 메모리 초과 코드를 수정하여 AC를 받은 코드 / 두번째 코드는 메모리 초과 코드이다.

소스 코드 : 

<AC>

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <memory.h>
 
using namespace std;
typedef pair<pair<string, int>, pair<int, int>> psi;
 
bool visit[220][220];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        memset(visit, false, sizeof(visit));
        string strA, strB, strC;
 
        cin >> strA >> strB >> strC;
 
        if (!strC.compare(strA + strB) || !strC.compare(strB + strA))
        {
            printf("Data set %d: yes\n", i);
            continue;
        }
        int lenA = strA.size();
        int lenB = strB.size();
        int lenC = lenA + lenB;
 
        bool yes = false;
 
        queue<psi> q;
 
        // q정보 :: string, string위치, strA위치, strB위치
        q.push({ {"", 0}, {0, 0} });
        q.push({ {"", 0}, {0, 0} });
 
        while (!q.empty())
        {
            string str = q.front().first.first;
            int pos = q.front().first.second;
            int posA = q.front().second.first;
            int posB = q.front().second.second;
 
            q.pop();
 
            // strC와 길이가 같고, str이 strC와 같으면 yes
            if (pos == lenC && str.compare(strC) == 0)
            {
                yes = true;
                break;
            }
 
            // posA만 더했을 때 visit하지 않았고, 현재 strA의 위치값과 strC의 위치값이 같다면
            // strA의 값을 넣어주고, strA의 다음 위치를 보게 해준다.
            if (posA < lenA && !visit[posA + 1][posB] && strA[posA] == strC[pos])
            {
                q.push({ {str + strA[posA], pos + 1}, {posA + 1, posB} });
                visit[posA + 1][posB]++;
            }
 
            if (posB < lenB && !visit[posA][posB + 1] && strB[posB] == strC[pos])
            {
                q.push({ {str + strB[posB], pos + 1}, {posA, posB + 1 } });
                visit[posA][posB + 1]++;
            }
        }
 
        if (yes)
            printf("Data set %d: yes\n", i);
        else
            printf("Data set %d: no\n", i);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

<Memory Overflow> 

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
 
using namespace std;
typedef pair<pair<string, int>, pair<int, int>> psi;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        string strA, strB, strC;
 
        cin >> strA >> strB >> strC;
 
        if (!strC.compare(strA + strB) || !strC.compare(strB + strA))
        {
            printf("Data set %d: yes\n", i);
            continue;
        }
        int lenA = strA.size();
        int lenB = strB.size();
        int lenC = lenA + lenB;
 
        bool yes = false;
 
        queue<psi> q;
 
        string tmp1;
        tmp1 += strA[0];
        string tmp2;
        tmp2 += strB[0];
 
        q.push({ {tmp1, 0}, {0, 0} });
        q.push({ {tmp2, 0}, {0, 0} });
 
        while (!q.empty())
        {
            string str = q.front().first.first;
            int pos = q.front().first.second;
            int posA = q.front().second.first;
            int posB = q.front().second.second;
 
            q.pop();
 
            if (str[pos] != strC[pos])
                continue;
 
            if (pos + 1 == lenC && str.compare(strC) == 0)
            {
                yes = true;
                break;
            }
 
 
                if(posA + 1 < lenA && strA[posA + 1] == strC[pos + 1])
                    q.push({ {str + strA[posA + 1], pos + 1}, {posA + 1, posB} });
 
                if(posB < lenB && strB[posB] == strC[pos + 1])
                    q.push({ { str + strB[posB], pos + 1 },{ posA + 1, posB } });
 
 
                if(posB + 1 < lenB && strB[posB + 1] == strC[pos + 1])
                    q.push({ {str + strB[posB + 1], pos + 1}, {posA, posB + 1 } });
 
                if(posA < lenA && strA[posA] == strC[pos + 1])
                    q.push({ { str + strA[posA], pos + 1 },{ posA + 1, posB } });
 
        }
 
        if (yes)
            printf("Data set %d: yes\n", i);
        else
            printf("Data set %d: no\n", i);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>