백준 1987 알파벳

알파벳 성공다국어 

문제

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

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

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

입력

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

출력

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

 

---

한칸씩 이동해보면서 이동 가능한 최대 경로를 찾아야 하는 문제이기 때문에 dfs를 이용한 백트레킹을 활용하면 문제를 풀 수 있다. 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int r, c;
vector<vector<char>> alpha;
vector<vector<bool>> visit;
vector<int> used_alpha(26, 0);
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int maxLength = 0;

void dfs(int x, int y, int length) {
    used_alpha[alpha[x][y] - 65] = 1;
    visit[x][y] = 1;
    maxLength = max(maxLength, length);

    for (int i = 0; i < 4; i++) {
        int newX = dx[i] + x;
        int newY = dy[i] + y;

        if (newX >= 0 && newX < r && newY >= 0 && newY < c
            && used_alpha[alpha[newX][newY] - 65] == 0
            && !visit[newX][newY]) {
            dfs(newX, newY, length + 1);
        }
    }

    // 백트래킹
    visit[x][y] = 0;
    used_alpha[alpha[x][y] - 65] = 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> r >> c;
    alpha.resize(r, vector<char>(c, 'A'));
    visit.resize(r, vector<bool>(c, 0));

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> alpha[i][j];
        }
    }

    dfs(0, 0, 1);
    cout << maxLength << "\n";

    return 0;
}

 

한칸씩 이동하며 재귀호출을 통해 dfs 탐색을 하면서 다른 경로의 탐색을 위해 for문 밖에서는visit배열과 사용된 알파벳 배열을 초기화하여 탐색에 문제가 없도록 하였다!!

 

bfs문제만 계속 풀다가 dfs문제를 만나니 당황스럽다.. dfs문제를 좀 더 풀어봐야겟당