[백준] 1987번: 알파

Solved.ac 골드5
https://www.acmicpc.net/submit/1987/76980470

설명

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

입력

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

출력

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

해결 Tip

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 백트래킹

우선 풀이의 토대가 되는 알고리즘은 그래프 탐색이다. 2D맵의 맨 왼쪽 위부터 시작하여 가장 멀리 갈 수 있는 경우를 탐색하면 된다.

이렇게 되면 남아있는 문제는 "말을 어디로 이동하게 할지"인데, 이는 현재 방문한 위치의 알파벳을 따로 배열에 저장하고 방문했는지 안 했는지를 판단하면 된다. 그리고, 방문 후 되돌아 올 때에는 해당 문자를 배열에서 지우면 된다.
(필자의 경우, 이를 boolean 배열로 구현하여 문자와 인덱스를 매칭하여방문한 경우 true, 아닌 경우를 false로 하여 구현했다.)

마지막으로, 말이 더 이상 움직일 수 없을 경우, 이동한 거리를 현재의 최댓값과 비교하여 더 큰 값을 최종 결과로 저장한다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> point; // (x, y)

int r, c;
char metrix[22][22];
point derivative[] = {
    {1, 0}, {-1, 0},
    {0, 1}, {0, -1}
};

int solve(point cur, bool check[], int maxCount) {
    // cout << "\n----- x=" << cur.first << ", y=" << cur.second << " -----\n";
    int result = -1;
    char c;
    point next;
    
    // cout << "val : " << metrix[cur.second][cur.first] << '\n';
    // cout << "visit : [ ";
    // for (char c='A' ; c <= 'Z' ; c++)
    //     cout << check[c-'A'] << ' ';
    // cout << "]\n";
    // cout << "neighbors :\n";
    for (point d : derivative) {
        next.first = cur.first + d.first;
        next.second = cur.second + d.second;
        c = metrix[next.second][next.first];
        // cout << "- (" << cur.first << ", " << cur.second << ") = " << c;

        if (c != 0 && !check[c-'A']) {
            // cout << " -> access\n\n";
            check[c-'A'] = true;
            result = max(result, solve(next, check, maxCount+1));
            check[c-'A'] = false;
        }
        // else cout << '\n';
    }

    // cout << "\n[$] max = " << max(maxCount, result) << "\n\n";
    return max(maxCount, result);
}

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

    // input
    cin >> r >> c;
    for (int y=1 ; y <= r ; y++) {
        for (int x=1 ; x <= c ; x++) {
            cin >> metrix[y][x];
        }
    }

    // solve
    bool check[26] = { 0,};
    check[metrix[1][1]-'A'] = 1;
    cout << solve({1,1}, check, 1);

    return 0;
}