[1987번] 알파벳

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. DFS

2. 문제 조건에 의한 처리 방법

문제 조건을 잘 이해하여하 하는 문제이다. 조금만 생각하면 바로 풀리지만, 조금만 잘못생각해도 꼬이는 문제이기도 하다.

문자를 밟았다는 것을 어떻게 코드화 시키느냐가 가장 중요한 문제인데

check[map[y][x] - 'A'] = 1; 이런식으로 1일때는 밟음, 0일때는 밟지 않음으로 형성하여 문제를 풀면 

간단하게 해결할 수 있다.

소스 코드 : 

#include <iostream>
#include <string>
 
using namespace std;
 
string map[21];
int check[26];
 
int n, m;
int maxValue = 0;
 
void dfs(int x, int y, int cnt)
{    
    if (check[map[y][x] - 'A'] == 0)
    {
        check[map[y][x] - 'A'] = 1;
        
        cnt > maxValue ? maxValue = cnt : 0;
 
        if (x + 1 < m) dfs(x + 1, y, cnt + 1);
 
        if (y + 1 < n ) dfs(x, y + 1, cnt + 1);
 
        if (x - 1 >= 0 ) dfs(x - 1, y, cnt + 1);
 
        if (y - 1 >= 0 ) dfs(x, y - 1, cnt + 1);
 
        check[map[y][x] - 'A'] = 0;
    }
}
 
int main()
{
    int cnt = 1;
 
    cin >> n >> m;
 
    while (getchar() != '\n') {}
 
    for (int i = 0; i < n; i++)
        getline(cin, map[i]);
 
    dfs(0, 0, cnt);
 
    cout << maxValue;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>