[BOJ] 1987번 알파벳 c++

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

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

---

입력 1
2 4
CAAB
ADCB

출력 1
3

---

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int R, C;
string v[20];
bool visited[26] = {false,};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int nx, ny;
int max_length = 0;

void dfs(int x, int y, int len) {
  max_length = max(max_length, len);
  for(int i = 0; i < 4; i++) {
    nx = x + dx[i];
    ny = y + dy[i];
    if(nx > -1 && nx < R && ny > -1 && ny < C) {
      int val = int(v[nx][ny]) - 65;
      if(!visited[val]) {
        visited[val] = true;
        dfs(nx, ny, len + 1);
        visited[val] = false;
      }
    }
  }
}

int main() {
  char tmp[20];
  scanf("%d %d", &R, &C);

  for(int i = 0; i < R; i++) {
    scanf("%s", tmp);
    v[i] = tmp;
  }

  visited[int(v[0][0]) - 65] = true;
  dfs(0, 0, 1);

  printf("%d\n", max_length);
}

이 문제는 특이하게 이차원 배열 크기만큼의 방문을 표시할 배열이 필요가 없다. 똑같은 알파벳을 두 번 이상 지나갈 수 없다는 조건이 이를 대신하기 때문이다. 첫 번째 시도에서는 지금까지 지나온 알파벳들을 문자열로 만들어서 파라미터로 넘겨주었으나 그렇게 하지 않아도 됐다.(알파벳의 범위가 한정적이라 그나마 나은 편이지만, 그렇지 않았다면 파라미터로 넘기는 건 굉장히 비효율적일 듯) 알파벳 개수와 동일한 배열을 만들어서 탐색을 하기 전에 방문 표시를 해두고, 방문이 끝나면 다시 원래대로 돌리면 되었다. 몇 년을 공부했지만 재귀 함수로 문제를 해결하는 건 알다가도 모르겠다.😅