문제

1987번: 알파벳

풀이

문제에서 출발 위치가 정해져있고, 보드의 크기가 최대 20 * 20으로 작아 완전탐색 백트래킹으로 풀 수 있었다.

같은 알파벳은 두 번 밟으면 안되기 때문에 이는 visited배열을 만들어 관리했다.
알파벳 A 부터 Z까지 각각의 인덱스를 담는 26크기의 visited 배열을 선언하여 사용했다.
다음 dfs 를 호출하기 전에 해당 칸의 알파벳을 visited 의 값을 참조하여 이미 방문했던 알파벳인지 아닌지 판단할 수 있다.

dfs를 호출할 때 depth값을 파라미터로 넘겨 얼마나 많이 이동했는지를 확인하고 가장 큰 값 저장하여 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int max(int a, int b){
    return a > b ? a : b;
}

struct Pos {
    int x;
    int y;

    bool operator==(Pos input){
        return x == input.x && y == input.y;
    }
    Pos operator+(Pos input){
        Pos res;
        res.x = this->x + input.x;
        res.y = this->y + input.y;
        return res;
    }
};

int n, m;
vector<string> board;
vector<int> visited(26, 0);
int answer = 0;

vector<Pos> dir = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };

bool OOB(Pos input){
    return input.x < 0 || input.x >= n || input.y < 0 || input.y >= m;
}

void dfs(Pos cur, int depth){
    answer = max(answer, depth);
    
    for (Pos d : dir){
        Pos next = cur + d;
        if ( OOB(next) ) continue;
        int nextVal = board[next.x][next.y] - 'A';
        if ( visited[(int)nextVal] != 0 ) continue;

        visited[nextVal]++;
        dfs(next, depth+1);
        visited[nextVal]--;
    }
}

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

    cin >> n >> m;
    for (int i=0; i < n; i++){
        string input;
        cin >> input;
        board.push_back(input);
    }

    Pos start = {0, 0};
    visited[board[start.x][start.y]- 'A'] += 1;
    dfs(start, 1);
    
    cout << answer << endl;

    return 0;
}