[백준] 알파벳

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

1987번: 알파벳

우선 문제부터 간단하게 요약하면,

 

보드의 각 칸에 알파벳 대문자가 적혀있는 상황입니다. 이 때, 알파벳이 겹치지 않게 가장 좌측 위에서 이동을 할 때, 총 몇개의 알파벳을 최대로 밟고 지나갈 수 있는지를 구하는 문제입니다.

 

<Solution>

bfs나 dfs를 사용해야 할 것으로 짐작할 수 있습니다. 여기에서 만약 bfs를 사용하게 되면, 저장해야 하는 상태로 판의 상태도 있을 것이기 때문에 관리가 어렵습니다. 그래서 dfs로 진행해야 할 것을 알 수 있습니다.

 

그러면 dfs를 사용하기 무리는 없는지 살펴봅시다. R과 C는 1 이상 20 이하로 주어지기 때문에 보드의 크기는 400칸이 max입니다. 더군다나, 알파벳의 종류는 26종류 밖에 없기 때문에 사실 최대로 깊어져봤자 26정도가 최대 깊이일 것입니다. (400정도의 깊이 또한 제가 봤을 때는 가능한 수준일 것 같기는 합니다.) 

 

그래서 dfs를 이용하여 만약 더이상 상하좌우 모두 진행이 불가능할 때의 깊이를 계속 최종 answer에 갱신해주는 형태로 구현하면 되는 것을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다.

 

<Solution>

#include <iostream>
#include <stack>

using namespace std;

char board[25][25];
int R, C;

int used[26];
int visited[25][25];
int ret_cnt;
int tmp_cnt;

int dir_r[] = {1, -1, 0, 0};
int dir_c[] = {0, 0, 1, -1};

void getinput(){
    cin >> R >> C;
    for(int i = 0; i<R; i++){
        cin >> board[i];
    }
}

void dfs(int r, int c){
    // no return condition for now

    int is_there_move = 0;

    for(int i = 0; i<4; i++){
        int new_r = r + dir_r[i];
        int new_c = c + dir_c[i];
        
        // if oob
        if(!(0<= new_r && new_r <R && 0<= new_c && new_c <C)) continue;
        // check if not visited and not used
        if(visited[new_r][new_c]) continue;
        if(used[board[new_r][new_c] - 'A']) continue;

        // 상태발전 가능
        is_there_move++; // 답 갱신위해

        tmp_cnt++;
        visited[new_r][new_c] = 1;
        used[board[new_r][new_c] - 'A'] = 1;
        dfs(new_r, new_c);
        tmp_cnt--;
        visited[new_r][new_c] = 0;
        used[board[new_r][new_c] - 'A'] = 0;
    }

    if(!is_there_move){
        // 움직임이 없었다 (4방향 모두 진행 불가)
        ret_cnt = max(ret_cnt, tmp_cnt);
        return;
    }

    return;

}

int main(){
    
    getinput();

    tmp_cnt = 1;
    visited[0][0] = 1;
    used[board[0][0] - 'A'] = 1;
    dfs(0, 0);

    cout << ret_cnt << endl;
}