[BOJ] 1987번 | 알파벳 (C++)

🔗문제 보러가기

1987번: 알파벳

 

🧑‍💻풀이 과정

 

DFS + 백트래킹으로 풀 수 있는 문제입니다. 처음에는 같은 문자 방문 여부를 위해 set을 이용했는데, 시간 초과가 나더라구요. 그래서 시간을 줄이기 위해 다른 방법을 생각했는데, 알파벳은 26개가 있고 각각 한 번씩만 방문할 수 있으니, vector<bool> Alphabet(26, false) 배열을 통해 방문 여부를 관리하니 통과가 되었습니다.

 

\(\mathrm{O(1)} \) 과 \( \mathrm{O(log \ N)} \) 의 탐색 비용 차이를 실감했던 문제였습니다.

아무튼, 다음과 같이 알고리즘을 구성해서 풀면 됩니다.

 

1. 문자열 보드판 정보를 2차원 배열에 저장한 후, 크기 26의 bool 배열(Alphabet)을 선언해 모두 false로 초기화한다.
2. 시작점 또한 길이에 포함되므로, Alphabet[0][0] = true 를 하고, 시작점을 기준으로 상하좌우 DFS 탐색을 시작한다.
   • 맵 밖을 벗어나거나 이미 방문했던 알파벳인 경우, 움직인 거리를 갱신하고 다음 방향으로 DFS 탐색 시작
   • (1)처음 방문하는 알파벳인 경우에는 방문 체크 해주고, (2)해당 알파벳 좌표부터 다시 상하좌우 탐색을 시작
   • (2) 탐색이 끝났다면, (1) 알파벳은 방문 해제 표시(백트래킹)

 

✏️ 소스 코드 및 결과

#include <iostream>
#include <vector>

using namespace std;
using Direction = pair<int, int>;

#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#define ALPHABET_COUNT 26

vector<Direction> Directions { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
vector<bool> Alphabet(ALPHABET_COUNT, false);
int R, C;

void BackTracking(const vector<vector<char>>& field, int& maxStep, int currentStep, int row, int col) {

    for (const auto& direction : Directions) {
        int nextRow = row + direction.first;
        int nextCol = col + direction.second;

        if (nextRow < 0 or nextRow >= R or nextCol < 0 or nextCol >= C) {
            maxStep = max(maxStep, currentStep);
            continue;
        }

        int index = field[nextRow][nextCol] - 'A';
        if (Alphabet[index]) {
            maxStep = max(maxStep, currentStep);
            continue;
        }

        Alphabet[index] = true;
        BackTracking(field, maxStep, currentStep + 1, nextRow, nextCol);
        Alphabet[index] = false;
    }
}

int GetMaximumAlphabet(const vector<vector<char>>& field) {
    int maxStep = 1;
    int index = field[0][0] - 'A';
    
    Alphabet[index] = true;
    BackTracking(field, maxStep, 1, 0, 0);
    return maxStep;
}

int main() {
    FAST_IO

    cin >> R >> C;
    vector<vector<char>> field(R, vector<char>(C));
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            cin >> field[r][c];
    
    int answer = GetMaximumAlphabet(field);
    cout << answer;

    return 0;
}