백준 1987번 - 알파벳 (C++)

해결 방법

누가봐도 DFS 문제라 DFS 돌림.
처음엔 string "ASCR" 이런식으로 밟은 알파벳 저장하고 find로 밟았는지 찾다가, 시간초과 나와서 밟았는지 체크용 전역 배열UsingAlphabet[26] 선언. 배열 인덱스는 A~Z다.

아쉬웠던 점

없음

코드

#include <iostream>
#include <string>
using namespace std;
 
char board[20][20];
 
pair<int,int> location[4] = {{0,1},{1,0},{0,-1},{-1,0}};
int returnCount = 0;
bool UsingAlphabet[26] = { false, };
int x, y; //사실 xy가 반대긴하다.
void Move(int startX, int startY, int count)
{
    if(returnCount < count)
        returnCount = count;
    
    for (int i = 0; i < 4; i++)
    {
        int nextX = startX + location[i].first;
        int nextY = startY + location[i].second;
        if(nextX < 0 || nextX > x-1 || nextY < 0 || nextY > y-1)
            continue;
        
        if(UsingAlphabet[board[nextX][nextY]-'A'] == false)
        {
            UsingAlphabet[board[nextX][nextY]-'A'] = true;
            Move(nextX, nextY, count+1);
        }
    }
    UsingAlphabet[board[startX][startY]-'A'] = false;   
}
 
int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> x >> y;
    for (int i = 0; i < x; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < y; j++)
        {
            board[i][j] = str[j];
        }
    }
    
    UsingAlphabet[board[0][0]-'A'] = true;
    Move(0,0, 1);
 
    cout << returnCount;
    return 0;
}