[백준] 1987번 알파벳

 

[적용한 알고리즘]

백트래킹, 재귀, DFS

 

[아이디어]

바로 전에 풀었던 문제랑 거의 흡사하다.

 

[생각의 흐름 / 절차] 

전 문제와 거의 동일

 

[교훈]

지금까지 나왔는 지 안나왔는지에 대한 중복 검사를 어떻게 할까 고민을 좀 했는데

그냥 간단하게 bool을 알파벳 길이만큼 해서 검사해주면 끝이다.

재밌다 재밌어

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int r, c;
int ans = -1;
char map[21][21];
bool visited[21][21];
bool overlap[26];
int dirx[] = {1, -1, 0, 0};
int diry[] = {0, 0, -1, 1};

void dfs(int x, int y, int cnt){
    if (ans < cnt){
        ans = cnt;
    }

    visited[x][y] = true;
    overlap[map[x][y] - 'A'] = true;

    for (int k = 0; k < 4; k++){
        int nx = x + dirx[k];
        int ny = y + diry[k];

        if (0 <= nx && nx < r && 0 <= ny && ny < c){
            if (!visited[nx][ny] && !overlap[map[nx][ny] - 'A']){
                dfs(nx, ny, cnt + 1);
            }
        }
    }

    visited[x][y] = false;
    overlap[map[x][y] - 'A'] = false;
}

int main(){
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; i++){
        scanf("%s", map[i]);
    }

    dfs(0, 0, 1);
    printf("%d\n", ans);


    return 0;
}