[백준 1987][C++] 알파벳 (Gold 4)

[문제보기]

 1987. 알파벳

1987번: 알파벳

 

[풀이과정]

한번 지나온 알파벳에 대해서는 다시 갈 수 없다는 문제에 대해서 필자는 bool alpha[26]라는 배열을 만들어 지나온 

알파벳에 대해 검사를 해주었다. 그리고 DFS 알고리즘을 이용하여 갈 수 있는 모든 경우의 수에 대해 연산을 

진행하면서 ans와 cnt값을 비교하면서 더 높은 값을 ans에 넣어주었다. 

 

DFS 알고리즘을 구현할 때 제일 주의해야되는 점은 재귀로 들어가기전 값을 변경하고 다시 빠져나올때는 값을 

이전 상태로 되돌리는 부분의 구현이 제일 중요하다. 필자는 if문 안에서 그것을 구현해주었다. 

[소스코드]

#include <iostream>
#include <cstring>
using namespace std;

int r, c, ans = 0;
char map[20][20] = {0};
bool alpha[26] = {0};
pair<int, int> movdir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void DFS(int y, int x, int cnt){
    ans = max(ans, cnt);

    for(int i=0; i<4; i++){
        int nexty = y + movdir[i].first;
        int nextx = x + movdir[i].second;

        if(nexty < 0 || r <= nexty || nextx < 0 || c <= nextx) continue;

        if(alpha[map[nexty][nextx] - 'A'] == true){
            alpha[map[nexty][nextx] - 'A'] = false;
            DFS(nexty, nextx, cnt+1);

            alpha[map[nexty][nextx] - 'A'] = true;
        }
    }
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);
    memset(alpha, true, sizeof(alpha));
    cin >> r >> c;

    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> map[i][j];
        }
    }
    
    alpha[map[0][0] - 'A'] = false;
    DFS(0, 0, 1);

    cout << ans ;
}

 

[해결 과정 중 실수한 부분]