[백준 c++] 1987 알파벳

문제 설명

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

• 문제
  세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
  말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
  좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

• 입력
  첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

• 출력
  첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

아이디어

DFS를 이용해서 풀었다.
visited는 이 경로까지 해당 알파벳이 들어가는지 체크하면 된다.
재귀 호출을 한 후에는 다시 visited를 0으로 바꿔줘야 한다.

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
using namespace std;
int n, m, cnt, mx = 1;
char a[21][21];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, -1, 0, 1};
int visited[26];
void go(int y, int x, int cnt)
{
    mx = max(mx, cnt);
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        int next = a[ny][nx] - 65;
        if (visited[next])
            continue;
        visited[next] = 1;
        go(ny, nx, cnt + 1);
        visited[next] = 0;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }
    int start = a[0][0] - 65;
    visited[start] = 1;
    go(0, 0, 1);
    cout << mx << "\n";
}