백준 1987 알파벳(dfs)

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

1987번: 알파벳

#include <iostream>

using namespace std;
const int MAX = 20;
int R, C;
string graph[MAX];
bool alphaVisited[26] = {false};
typedef struct
{
    int x, y;
} Dir;
Dir Dirmove[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int ans;

void dfs(int x, int y, int cnt)
{
    ans = max(ans, cnt);

    for (int i = 0; i < 4; i++)
    {
        int nextX = x + Dirmove[i].x;
        int nextY = y + Dirmove[i].y;
        if (0 <= nextX && nextX < R && 0 <= nextY && nextY < C && !alphaVisited[graph[nextX][nextY] - 'A'])
        {
            alphaVisited[graph[nextX][nextY] - 'A'] = true;
            dfs(nextX, nextY, cnt + 1);
            alphaVisited[graph[nextX][nextY] - 'A'] = false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        cin >> graph[i];
    int cnt = 1;
    alphaVisited[graph[0][0] - 'A'] = true;
    dfs(0, 0, cnt);
    cout << ans;
}

굉장히 어려우면서도 재밌었다. 단순한 dfs 문제만 풀다가 백트래킹이 가미된 문제를 처음 풀다보니 너무 많이 헤매긴 했지만 얻어가는게 많았던 문제다.

 

입력이 대문자로만 이루어지기 때문에 -'A'를 하게 되면 A에서 부터 Z까지 0~26이 된다. 이를 이용하면 더 직관적인 코드를 짤 수 있다.