[BOJ] 1987 알파벳

문제접근

2차원에서 상하좌우 방향으로 갈 수 있는 정점의 개수를 카운팅하는 문제

소스코드

#include <iostream>
#include <string>
#include <array>
#include <vector>
using namespace std;
char v[21][21];

int r,c;

bool check_range(int x, int y) {
//    cout << "x: " << x << ", y:" << y << "\n";
    return x < 0 || x >= c || y < 0 || y >= r;
}

// 첫번째 파라미터를 참조가 아니게 선언함. 이는, alpha 변수가 상하좌우로 갔을 시나리오가 별개이기 때문.
int solution(array<bool,28> alpha, int x, int y) {
    // 좌표 범위가 어긋나거나, 이미 방문한 경험이 있으면 탈락
    if(check_range(x, y) or alpha[v[y][x]-'A']) return 0;

    // 방문한 알파벳 저장
    alpha[v[y][x] - 'A'] = true;

    int result1 = 0, result2 = 0;

    // 상하좌우에서 가장 많이 가는 횟수 + 현재 위치값(1) 반환
    result1 = max(solution(alpha, x+1, y), solution(alpha, x-1, y));  
    result2 = max(solution(alpha, x, y+1), solution(alpha, x, y-1));
    //cout << "result: " << result1 << ", result2:" << result2 << endl;
    return max(result1, result2) + 1;
}

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

    cin >> r >> c;
    for(int i = 0; i < r; i++) {
        string temp;
        cin >> temp;
        for(int j = 0; j < temp.length(); j++){
            v[i][j] = temp[j];
        }
    }

    array<bool,28> alpha;
    alpha.fill(0);

    cout << solution(alpha,0, 0);
    return 0;
}