BOJ 1987 : 알파벳

3줄요약

• dfs
• 백트래킹
• 문자열

 

서론

 

이 문제는 dfs + 백트래킹의 기본형 문제라고 볼 수 있다.

 

본론

 

우리가 이 문제를 풀 때 알아야 하는 것은 한 가지 뿐이다.

• dfs (응용)

 

어짜피 알파벳 대문자는 26개이기 때문에, dfs 완전탐색을 돌려도 되는 문제이다. (시간복잡도가 그렇게 크게 안 나온다.)

지금까지 어떤 알파벳을 체크했는지 알 수 있다면, 같은 문자가 두 개 나왔을 때 백트래킹을 할 수 있으므로, 그 방식으로 문제를 풀면 된다.

 

#include <iostream>
#include <string>

using namespace std;
#define MAXCHK (65 + 26 + 1)

int Y, X;
int graph[21][21];
bool check[MAXCHK]; // just for init

int dfs(int x, int y, bool chk[MAXCHK]) {

    if (x <= 0 || x > X || y <= 0 || y > Y) return 0;
    int idx = graph[y][x];
    if (chk[idx]) return 0;

    bool nxt[MAXCHK]; for (int i = 65; i <= 65 + 26; i++) nxt[i] = chk[i];
    nxt[idx] = true;

    return max( dfs(x + 1, y, nxt), max( dfs(x - 1, y, nxt), max( dfs(x, y + 1, nxt), dfs(x, y - 1, nxt) ) ) ) + 1;
}

int main() {
    scanf("%d %d", &Y, &X);

    for (int i = 1; i <= Y; i++) {
        string inp; cin >> inp;
        for (int j = 0; j < X; j++) {
            graph[i][j + 1] = inp[j];
        }
    }

    int ans = dfs(1, 1, check);
    cout << ans;
}

 

결론

 

 

마치 정올 1번문제를 보는 느낌이였다. 그만큼 쉬웠다...

난이도(개인적): Silver I (Up to Gold V)

난이도(객관적): Gold IV

 

다음에 풀 것: 16565번: N포커 (acmicpc.net) (Gold I)

 

 

Contact: How2Contact (tistory.com)