[ SWEA 7699 ] 수지의 수지 맞는 여행 (C++)

SWExpertAcademy의 수지의 수지 맞는 여행(7699 / D4) 문제이다.

[ 문제풀이 ]

1) 이 문제는 (1, 1)에서 시작해서 가장 많은 명물을 몇 개 까지 볼 수 있는지를 찾아내야 하는 문제이다.

   본인은 깊이우선탐색(DFS)를 이용해서 접근해 보았다.

   탐색의 조건은 딱 한가지이다. "탐색하고자 하는 알파벳이, 기존에 방문한 알파벳인지?" 만 체크해주면 된다.

   문제도 코드도 그리 복잡하지 않으니 소스코드를 참고해도 충분히 이해 될 거라 생각한다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int Answer;
int R, C;
char MAP[MAX][MAX];
bool Alphabet[26];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Answer = 0;
    memset(Alphabet, false, sizeof(Alphabet));
}
 
void Input()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void DFS(int x, int y, int Cnt)
{
    Answer = Bigger(Answer, Cnt);
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < R && ny < C)
        {
            if (Alphabet[MAP[nx][ny] - 'A'] == false)
            {
                Alphabet[MAP[nx][ny] - 'A'] = true;
                DFS(nx, ny, Cnt + 1);
                Alphabet[MAP[nx][ny] - 'A'] = false;
            }
        }
    }
}
 
void Solution()
{
    Alphabet[MAP[0][0] - 'A'] = true;
    DFS(0, 0, 1);
}
 
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;
}