[백준] 1987 알파벳 c++

 

 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX = 21;
int r, c;
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int alpha[26];
char arr[MAX][MAX];
int answer;
 
void dfs(int x, int y, int cnt) {
    answer = max(answer, cnt);
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        int idx = (int)arr[nx][ny] - 65;
 
        if (nx<0 || nx>=r || ny<0 || ny>=c) // 범위 밖인 경우
            continue;
        if (alpha[idx]) //알파벳이 이미 있는 경우
            continue;
 
        alpha[idx] = 1; //선택
        dfs(nx, ny, cnt + 1);
        alpha[idx] = 0; //선택 해제
    }    
}
int main()
{
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> arr[i][j];
        }
    }
 
    alpha[(int)arr[0][0] - 65] = 1;
    dfs(0, 0, 1);
    cout << answer;
}