BOJ 1987번 알파벳

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

github : https://github.com/junho0956/Algorithm/blob/master/1987/1987/%EC%86%8C%EC%8A%A4.cpp

 

DFS 를 이용한 백트래킹의 기본문제였습니다.

 

#include <iostream>
using namespace std;
 
int R, C, Max;
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };
char arr[20][20];
bool visit[26];
 
void dfs(int y, int x, int cnt) {
    
    Max = Max < cnt ? cnt : Max;
 
    for (int i = 0; i < 4; i++) {
        int yy = y + my[i];
        int xx = x + mx[i];
        if (yy >= 0 && yy < R && xx >= 0 && xx < C && !visit[arr[yy][xx]-'A']) {
            visit[arr[yy][xx] - 'A'] = true;
            dfs(yy, xx, cnt + 1);
            visit[arr[yy][xx] - 'A'] = false;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cin >> arr[i][j];
 
    visit[arr[0][0] - 'A'] = true;
    dfs(0, 0, 1);
    cout << Max;
 
    return 0;
}