[C++] 백준 1987번 - 알파벳

 

📖 문제

 

📋 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
vector<bool> check(26, false);
int ans, r, c;

void go(int x, int y, int cnt, vector<vector<char>> &a)
{
    ans = max(ans, cnt);
    for (int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c)
            continue;
        int value = a[nx][ny];
        if (check[value - 'A'] == true)
            continue;
        check[value - 'A'] = true;
        go(nx, ny, cnt + 1, a);
        check[value - 'A'] = false;
    }
}
int main(int argc, const char *argv[])
{
    cin >> r >> c;
    vector<vector<char>> a(r, vector<char>(c, ' '));
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> a[i][j];
        }
    }

    check[a[0][0] - 'A'] = true;
    go(0, 0, 1, a);
    cout << ans << '\n';
    return 0;
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

DFS로 탐색하면서 가장 긴 거리들을 갱신하여 정답을 출력하였습니다.

굳이 보드판 방문 체크 2차원 배열을 만들지 않고 알파벳 사용 체크 배열만 사용한 이유는
어차피 이미 지나간 곳의 알파벳의 사용이 체크되어 있으므로 지나오지 않는 곳으로만 탐색하기 때문입니다. 

 

 

🔗 링크

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

1987번: 알파벳