[백준][1987] 알파벳

이 포스트는 백준 사이트의 알파벳 문제 풀이입니다.

문제

해결 과정

이 문제는 DFS와 아스키 코드를 사용한 방문 기록 배열을 이용하여 해결할 수 있습니다.

DFS를 재귀적으로 실행하면서 방문한 거리까지를 최댓값과 비교하면 됩니다.

여기서 중요한 것은 방문했던 알파벳은 다른 위치에 있더라도 재방문이 불가능하다는 것 입니다.
따라서 맵이 대문자 알파벳만 주어진다는 점을 활용하여
방문 기록을 남기도록 하였습니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int dir_row[4]{-1, 1, 0, 0};
int dir_col[4]{0, 0, -1, 1};

int R, C, result = 1;
vector<vector<char>> board(21, vector<char>(21, ' '));
vector<bool> vis_alpha(27, false);
void DFS(int row, int col, int cnt);


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C;

    for(int row = 0; row < R; ++row) {
        for(int col = 0; col < C; ++col) {
            cin >> board[row][col];
        }
    }
    
    vis_alpha[board[0][0] - 'A'] = true;
    DFS(0, 0, 1);

    printf("%d", result);

    return 0;
}


void DFS(int row, int col, int cnt) {
    vis_alpha[board[row][col] - 'A'] = true;

    result = max(result, cnt);

    for(int dir = 0; dir < 4; ++dir) {
        int new_row = row + dir_row[dir];
        int new_col = col + dir_col[dir];

        if(new_row < 0 || new_row >= R || new_col < 0 || new_col >= C) 
            continue;
        if(vis_alpha[board[new_row][new_col] - 'A'])
            continue;

        DFS(new_row, new_col, cnt + 1);
    }

    vis_alpha[board[row][col] - 'A'] = false;
}

실행 결과