1987 알파벳 (성공)

#include<iostream>
#define MAX 20
 
using namespace std;
 
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
char mat[MAX][MAX];
bool alphabet[26];
int maxLength = -1;
int R, C;
 
 
bool isInside(int x, int y) {
    return x >= 0 && x < R && y >= 0 && y < C;
}
 
// sol 1)
void dfs(int x, int y, int length) {
    
    if (length >= maxLength)
        maxLength = length;
 
 
    alphabet[mat[x][y] - 65] = true;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isInside(nx, ny) && alphabet[mat[nx][ny] - 65] == false)
            dfs(nx, ny, length + 1);
    }
    // ★★★★★
    alphabet[mat[x][y] - 65] = false;
}
 
/* // sol 2)
void backTracking(int x, int y, int length) {
 
    if (alphabet[mat[x][y] - 65] == true)
        return;
 
    if (maxLength > 25)
        return;
 
    alphabet[mat[x][y] - 65] = true;
 
    if (length >= maxLength)
        maxLength = length;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isInside(nx, ny))
            backTracking(nx, ny, length + 1);
    }
 
    alphabet[mat[x][y] - 65] = false;
}*/
 
int main() {
 
    cin >> R >> C;        // R:세로, C:가로
 
    for (int i = 0; i < R; i++) {
        cin >> mat[i];
    }
 
 
    dfs(0, 0, 1);
 
    cout << maxLength;
 
    return 0;
}

<개선과정>

1. 

// ★★★★★

    alphabet[mat[x][y] - 65] = false;

이 부분 빼먹으면 아예 틀렸습니다 뜸.

2.

처음엔 

sol 1) dfs 방식 이 완전탐색이라서 시간초과 나는 줄 알고,

sol 2) backTracking 방식으로 바꿨는데 또 시간초과 나는것이다.

알고보니 이 부분을 이중 for문으로 해놨어서 시간초과 뜨는거였음......으 멍청멍청.. 이런실수 처음임. 

첫번째 시도했을땐 안썼던건데 굳이 언제 추가했담..? 쓴 기억도안나 ㅋㅋ

 for (int i = 0; i < 4; i++) {

for (int j=0; j<4; j++) {

        int nx = x + dx[i];

        int ny = y + dy[i];

        if (isInside(nx, ny))

            backTracking(nx, ny, length + 1);

    }

}

이중 for문 없애고 나니까 두가지 방법 모두 맞았습니다 뜸.