[ SWEA 7396 ] 종구의 딸이름 짓기 (C++)

SWExpertAcademy의 종구의 딸이름 짓기(7396 / D5) 문제이다.

[ 문제풀이 ]

보드의 왼쪽위에서 오른쪽 아래로 가는 경로에 있는 알파벳들을 순서대로 나열해서 이름을 만들 때, 가장 빠른 이름을 찾아야

하는 문제이다. 본인은 이 문제를 완전탐색으로 접근하였다. 그 중에서 너비우선탐색(BFS)를 통해서 접근해 보았다.

문제에서 조건을 보게 되면 '2방향'으로 움직일 수 있다고 되어있다. 그런데 '2방향'을 모두 탐색해준 것은 아니고 '정답일 가능성이

있는 방향'으로만 탐색해 주었다.

예를 들면 현재 칸에서 아래쪽으로 가면 'c'가 있고, 오른쪽으로 가면 'b'가 있다고 가정해보자.

과연, 현재 칸에서 아래쪽으로 간다면 정답이 될 수 있을까 ?? 절대로 정답이 될 수 없다. 왜냐하면 ! 오른쪽으로 갔을 때 'c'보다

더 작은 'b'가 존재하기 때문에 최소한 정답이 되기 위해서는 지금 당장 눈앞에 있는 가장 작은 값을 찾아 가야 한다는 것이다.

쉽게 생각해보면 이렇게 생각해볼 수 있다. 'azaaa' 와 'abzzz' 가 정답의 후보라면 정답이 무엇일까 ? 바로 'abzzz'이다.

즉 ! 첫 번째 'a'에서 'b'와 'z'중에서 더 빠른 값인 'b'로만 가더라도 정답을 찾아낼 수 있기 때문에, 'z'로 가는 경우를 탐색에 포함시키지 않아도 되는 것이다.

물론 ! 알파벳이 2개가 같다면 2방향 모두 탐색을 해줘야 한다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 2000
using namespace std;
 
int N, M;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
string Answer;
 
int dx[] = { 0, 1 };
int dy[] = { 1, 0 };
 
void Initialize()
{
    Answer = "";
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
 
void Solution()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(0, 0));
    Visit[0][0] = true;
    Answer = Answer + MAP[0][0];
    bool Flag = false;
 
    while (Q.empty() == 0)
    {
        int Q_Size = Q.size();
        char Min_Value = 'z';
        vector<pair<int, int>> V;
 
        for (int i = 0; i < Q_Size; i++)
        {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();
            
            if (x == N - 1 && y == M - 1)
            {
                Flag = true;
                break;
            }
 
 
            for (int i = 0; i < 2; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M)
                {
                    if (Visit[nx][ny] == false)
                    {
                        if (MAP[nx][ny] <= Min_Value)
                        {
                            if (MAP[nx][ny] < Min_Value) V.clear();
                            V.push_back(make_pair(nx, ny));
                            Visit[nx][ny] = true;
                            Min_Value = MAP[nx][ny];
                        }
                    }
                }
            }
        }
        for (int i = 0; i < V.size(); i++) Q.push(V[i]);
        if (Flag == false) Answer = Answer + Min_Value;
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}