[C++] 알파벳 (백준 1987번)

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

 

#include <iostream>
#include <vector>
using namespace std;

int r, c;
vector<string> m;
bool vst[26];
int maxc = 0;

int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};

void dfs(int curi, int curj, int cnt) {
    if (cnt > maxc) maxc = cnt;
    for (int k = 0; k < 4; k++) {
        int nxti = curi + di[k];
        int nxtj = curj + dj[k];
        if (nxti >= 0 && nxti < r && nxtj >= 0 && nxtj < c && !vst[m[nxti][nxtj] - 'A']) {
            vst[m[nxti][nxtj] - 'A'] = true;
            dfs(nxti, nxtj, cnt + 1);
            vst[m[nxti][nxtj] - 'A'] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> r >> c;

    m = vector<string>(r);
    for (int i = 0; i < r; i++) {
        cin >> m[i];
    }

    vst[m[0][0] - 'A'] = true; 
    dfs(0, 0, 1);

    cout << maxc << '\n';
}

전형적인 dfs 문제였다. 알파벳 보드 m 배열과 해당 알파벳을 방문했는지 여부 vst 배열 등을 전역으로 정의한다. dfs 함수에서는 상하좌우로 움직이면서 vst 배열을 체크하고 만약 갈 수 있다면 해당 알파벳의 vst를 true로 만들고 dfs 함수를 호출 후 다시 vst를 false로 만드는 식으로 구현했다. (AC)