백준 1987번: 알파벳 C++코드(DFS, Backtracking, 백트래킹)

#include<iostream>
#include<algorithm>

using namespace std;

int alphabet[26] = {0,};
char graph[21][21] = {0,};
int r,c;
int result = 0;
int y[4] = {0,0,-1,1};
int x[4] = {-1,1,0,0};

void dfs(int ny, int nx, int cnt){
    if(result < cnt){
        result = cnt;
    }
    for(int i=0; i<4; i++){
        int py = ny + y[i];
        int px = nx + x[i];
        if(0<= py & py < r & 0<= px & px < c & alphabet[graph[py][px]-65] == 0){
            alphabet[graph[py][px]-65] = 1;
            dfs(py, px, cnt+1);
            alphabet[graph[py][px]-65] = 0;
        }
    }
}

int main(){
    cin >> r >> c;
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> graph[i][j];
        }
    }
    alphabet[graph[0][0]-65] = 1;
    dfs(0,0,1);
    cout << result;
}

설명

BFS로 하면 귀찮아지는 이유는 문제상에서 한번 알파벳을 지나간 자리는 다시 지나갈 수 없기 때문에, 큐를 이용한 BFS로 구현하면, 큐에 카운트까지 같이 담고, 그 카운트를 따로 배열에 다 할당해줬다가, 함수가 완전히 끝났을 때, 카운트 중 가장 큰 값을 빼는 그런 자잘한 연산이 많아진다. 그래서 백트래킹을 활용하는 DFS를 사용해야하지않나싶다. (물론 필자는 그냥 분류에 깊이 우선 탐색이라고 쓰여있어서 그렇게 풀었다.)