[백준] 알파벳 1987번 (c++)

출처 : 1987번: 알파벳 (acmicpc.net)

1987번: 알파벳

풀이 방법

bfs로 풀지 dfs로 풀지 고민하다 지금 까지 지나온 알파벳을 저장하고 알파벳 방문 여부를 판단하기에

dfs가 더 적합할 거 같아서 dfs 로 풀이하였다.

알파벳은 26개의 배열을 만들어 방문했으면 배열에 1로 두고 두 번 방문하지 않게 하였다.

그리고  백트레킹을 활용하여 더 이상 갈 곳이 없으면 배열을 다시 초기화하여서 다른 방향에서 방문을 할 수 있도록

하였다.

#include<bits/stdc++.h>
using namespace std;

vector<string> board;
int alphabet [26];
int visited[21][21];
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};
int R, C, ans = 0;

void dfs(int y,int x, int cnt) {
    if (cnt > ans) ans = cnt;
    for (int i = 0;i < 4;i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 0 && ny < R && nx >= 0 && nx < C && visited[ny][nx] == 0) {
            if (alphabet[board[ny][nx] - 'A'] == 0 ) {
                visited[ny][nx] = 1;
                alphabet[board[ny][nx] - 'A'] = 1;
                dfs(ny, nx, cnt + 1);
                visited[ny][nx] = 0;
                alphabet[board[ny][nx] - 'A'] = 0;
            }
        }
    }    
}
int main(){
    memset(visited, 0, sizeof(visited));
    memset(alphabet, 0, sizeof(alphabet));
    cin >> R >> C;
    for (int i = 0;i < R;i++) {
        string str;
        cin >>str;
        board.push_back(str);
    }
    visited[0][0] = 1;
    alphabet[board[0][0] - 'A'] = 1;
    dfs(0, 0, 1);
    cout << ans;
    return 0;
}