1987번 백준(Baekjoon)

<문제 풀이>

같은 알파벳을 지날 수 없다는 조건이 있으므로 dfs를 통해 풀었다.

먼저 입력을 char형으로 받아 맵을 만들었고, 이후 visit의 비교를 위해 'A'가 아스코드값으로 65이므로

map[x][y]-65를 통해 방문여부를 판단하였다.

<정답 코드>

#include <iostream>
#include <vector>
 
#define MAX 21
 
using namespace std;
 
int row, col;
char map[MAX][MAX];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int visit[26];
vector<pair<int, int>> v;
int ans;
 
void dfs(int cnt)
{
    int x = v.front().first;
    int y = v.front().second;
    v.pop_back();
    for (int i = 0; i < 4; i++) {
        if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] < row && y + dy[i] < col)
            if (visit[map[x + dx[i]][y + dy[i]] - 65] == 0) {
                visit[map[x + dx[i]][y + dy[i]] - 65] = 1;
                v.push_back({ x + dx[i], y + dy[i] });
                dfs(cnt + 1);
                visit[map[x + dx[i]][y + dy[i]] - 65] = 0;
            }
    }
    if (ans <= cnt)
        ans = cnt;
    return;
}
 
int main()
{
    cin >> row >> col;
    for (int r = 0; r < row; r++)
        for (int c = 0; c < col; c++)
            cin >> map[r][c];
 
    visit[map[0][0] - 65] = 1;
    v.push_back({ 0,0 });
    dfs(1);
    cout << ans;
    return 0;
}