[백준 C++] 1987 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

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

출력

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

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

풀이

처음에 dfs가아닌 bfs로 문제를 접근하니, 모든 상태에대한 정보를 전부 저장해야하고 계산해야하니 시간초과, 메모리초과등이 생겼다..
dfs로 한번에 탐색하고 탐색이후에는 방문한 이력을 초기화하는 방법으로 다시 문제를 풀어보았다.
먼저, RxC크기의 visited배열을 사용할 필요ㄱ ㅏ없었다.
현재까지 방문한 알파벳에대한 정보를 알면, 겹칠경우 탐색을 종료하고(백트래킹?) 다시 상위로 돌아가 탐색을 하면 되기 때문.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::stack; using std::queue;
using std::deque; using std::string; using std::pair;
using std::sort;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef pair<string, string> pss;

int R, C;
char** map;
bool alphabet[26];
int res = 0;
int dx[] = {0, 1, 0, -1};
int dy[] = { 1, 0, -1, 0 };

void init();
void func();
void dfs(int x, int y, int cnt);
void init() {
    scanf("%d%d", &R, &C);
    map = new char* [R];
    for (int i = 0; i < R; i++) {
        char c;
        scanf("%c", &c); //줄바꿈문자 제거
        map[i] = new char[C];
        for (int j = 0; j < C; j++) {
            scanf("%c", &c);
            map[i][j] = c;
        }
    }
}

void func() {
    alphabet[map[0][0] - 'A'] = true;
    dfs(0, 0, 1);
    printf("%d", res);
}

void dfs(int x, int y, int cnt) {
    if (cnt > res) res = cnt;

    for (int d = 0; d < 4; d++) {
        int xx = x + dx[d];
        int yy = y + dy[d];
        if (xx < 0 || yy < 0 || xx == R || yy == C || alphabet[map[xx][yy] - 'A']) continue;
        alphabet[map[xx][yy] - 'A'] = true; //탐색전 체크
        dfs(xx, yy, cnt + 1); //탐색
        alphabet[map[xx][yy] - 'A'] = false; //탐색후 체크 해제
    }
}

int main(void) {
    init();
    func();


    return 0;
}