백준 1987 알파벳 (C++)

1987번: 알파벳

대충 보면 BFS문제처럼 보일 수 있지만 백트래킹을 이용한 DFS 문제이다. 문제에서 한번 방문한 종류의 알파벳은 방문할 수 없다고 명시되어 있기때문에 방문한 알파벳들을 저장할 필요가 있다. BFS로는 이부분이 힘들기에 DFS를 사용했다. visit배열을 사용해 알파벳마다 false를 할당하고 방문하면 true로 바꿔주었다. 지나온 칸 수는 n에 저장되어 함수가 호출될 때 마다 최댓값을 res에 저장해주었다.
간단한 백트래킹 문제여서 어렵지않게 풀 수 있었다.

#include <iostream>
#include <algorithm>

using namespace std;

int R, C, res = 0;
char A[21][21];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool visit[26];

void dfs(int n, int y, int x) {
    res = max(res, n);

    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
        if (visit[A[ny][nx] - 'A']) continue;

        visit[A[ny][nx] - 'A'] = true;
        dfs(n + 1, ny, nx);
        visit[A[ny][nx] - 'A'] = false;
    }
}

void solution() {
    visit[A[0][0] - 'A'] = true;
    dfs(1, 0, 0);

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        string a;
        cin >> a;
        for (int j = 0; j < C; j++) {
            A[i][j] = a[j];
        }
    }

    solution();

    return 0;
}