[ 백준 1987 ] 알파벳 (C++)

백준의 알파벳(1987) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 입력으로 주어지는 맵에서, 알파벳들을 한번씩만 밟고 지나갈 수 있는 최대 칸 수를 구하는 문제이다.

   백트래킹 문제로서, 전체적인 풀이과정부터 알아보자.

   일단 시작하는 (0, 0)에 있는 알파벳은 무조건 밟을 수 밖에 없다. 이 알파벳을 안 밟고 문제를 푸는 과정은 존재할 수가

   없기 때문에 (0, 0)에 있는 알파벳은 무조건 밟은 걸로 체크를 해주고 시작해야 한다.

   본인은 표시를 위해서 Visit[] 1차원 배열을 사용했으며, 크기는 알파벳의 갯수인 26만큼 할당해 주었다.

  

   이후, 상하좌우로 밟지 않은 알파벳들이 있는 곳으로 움직이면서 알파벳을 밟았다고 체크를 해주면서 진행 후,

   다시 알파벳을 밟지 않은 것으로 바꿔주고 다른 경로에 대해서 탐색을 해줘야 한다.

  

   예를 들어서 이러한 형태의 맵이 있다고 생각해보자. 만일, (0, 0) 지점인 C에서 (1, 0) 지점인 빨강색 A로 간다고

   생각해보자. 그렇다면, 'C'와 'A'는 이미 밟은 알파벳이므로 더 이상 밟을 수 없을 것이고, 결과적으로 총 2칸 밖에 갈 수가

   없다. 하지만 파랑색 A에서 생각해보자. 빨강색 A때문에 이미 밟은 알파벳이 아니였다면, 2칸보다는 훨씬 더 많은 칸을

   갈 수가 있을 것이다. 따라서 빨강색 'A'를 밟은 순간, "A는 이미 밟았으니까 더 이상 못밟습니다 !" 가 아니라

   "다른 경로로 한번 가볼게요. 'A'는 밟지 않았으니 다시 밟으셔도 됩니다" 라는 식으로 코드를 구현해줘야 한다.

  

   이 부분에 대한 백트래킹만 잘 구현해 준다면 코드 내용은 그리 어렵지 않을 것이다. DFS로 구현을 하였고, Visit[] 배열을

   통해서 밟은 알파벳을 체크해주었다.

[ 소스코드 ] 

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int R, C, Answer;
char MAP[MAX][MAX];
bool Visit[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 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 (Visit[MAP[nx][ny] - 'A'] == false)
            {
                Visit[MAP[nx][ny] - 'A'] = true;
                DFS(nx, ny, Cnt + 1);
                Visit[MAP[nx][ny] - 'A'] = false;
            }
        }
    }
}
 
void Solution()
{
    Visit[MAP[0][0] - 'A'] = true;
    DFS(0, 0, 1);
 
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}