백준 1987: 알파벳

문제 링크 : https://www.acmicpc.net/problem/1987

1987번: 알파벳

 문제설명 

 

(1,1)에서 탐색시작하여 알파벳 사용하지 않은 곳만 가야됨

그래서 이동 할 수있는 가장 많은 칸의 값을 return .

 

 알고리즘 

 

기본적으로 DFS탐색을 하는데 백트래킹을 이용하여 최대값을 갱신해준다.

 

 코드 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
char map[21][21];
 
int check[26] = { 0 };
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int R, C,cnt = 0;
void dfs(int y, int x, int count) {
    cnt = max(count, cnt);
 
    //4방향 탐색
    for (int i = 0; i < 4; i++) {
        int next_x = x + dx[i];
        int next_y = y + dy[i];
 
        if (next_x >= 0 && next_x < C && next_y >= 0 && next_y < R) {
            //알파벳을 사용하지 않은곳만 탐색
            if (!check[map[next_y][next_x] - 'A']) {
                
                check[map[next_y][next_x] - 'A'] = 1;
                dfs(next_y, next_x, count + 1);
 
                //백트래킹
                check[map[next_y][next_x] - 'A'] = 0;
            }
 
        }
    }
 
}
 
int main(){
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
        }
    }
    
    //시작점 알파벳 체크
    check[map[0][0] - 'A'] = 1;
    
    //시작하는 카도 포함이므로 count는 1로시작
    dfs(0, 0, 1);
    cout << cnt;
 
}