[백준 1987] 알파벳

0. 제목

• 백준 1987 알파벳
• BOJ 1987 알파벳
• C++ 1987 알파벳

---

1. 문제

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

---

2. 풀이

• DFS와 백트래킹을 사용하는 문제이다.
• 방문 여부를 체크할 때 A~Z, 총 26개의 인덱스를 가진다.
• 상하좌우 이동하며, 방문하지 않았다면 true로 체크한다.
• 방문한적이 있다면 무시하고 넘어간다.
• 가장 깊게 들어간 최댓값이 정답이다.

---

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
char arr[21][21];
bool visitedAlpha[26];//A~Z
int R, C;
 
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
 
int dfs(int x, int y, int check){
    visitedAlpha[check-'A'] = true;
    
    int cnt = 0;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        
        int next = arr[nx][ny];
        if(!visitedAlpha[next-'A']){
            visitedAlpha[next-'A'] = true;
            cnt = max(cnt, dfs(nx, ny, next));
            visitedAlpha[next-'A'] = false;
        }
    }
    return cnt + 1;
}
 
int main(int argc, const char * argv[]) {
    cin >> R >> C;
    
    for(int i = 0; i < R; i++){
        string s;
        cin >> s;
        for(int j = 0; j < s.length(); j++){
            arr[i][j] = s[j];
        }
    }
   
    cout << dfs(0, 0, arr[0][0]) << '\n';
    
    return 0;
}