[BOJ] 백준 1987 알파벳

문제 링크

www.acmicpc.net/problem/1987

1987번: 알파벳

 

풀이

모든 경로를 찾기 위해 dfs를 돌려줍니다.

얼핏 생각하면 복잡도가 터져 나갈 것 같지만 격자 그래프, 작은 범위, 지나간 알파벳은 다시 못 지나간다는 제한 사항 때문에 시간 안에 가능합니다.

 

저는 알파벳 체킹을 비트 마스크로 했지만 체크 배열을 만들어도 무방합니다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
string p[22];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool isValid(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int go(int s, int x, int y) {
    int ret = 0;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (!isValid(nx, ny)) continue;
        int num = p[nx][ny] - 'A';
        if (s & (1 << num)) continue;
        ret = max(ret, go(s | (1 << num), nx, ny));
    }
    return ret + 1;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    cout << go(1 << (p[0][0] - 'A'), 0, 0);
}