# 백준 : 알파벳 (1987)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1987_alphabet)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

int R, C;
char map[21][21];
bool visit[21][21];
bool alphabet[26];
int maximumcount;

void DFS(int r, int c, int result) {
    maximumcount = max(maximumcount, result);
    visit[r][c] = true;
    alphabet[map[r][c] - 'A'] = true;
    if((r > 0) && !visit[r-1][c] && !alphabet[map[r-1][c]-'A'])       DFS(r-1, c, result+1);
    if((r < R-1) && !visit[r+1][c] && !alphabet[map[r+1][c]-'A'])     DFS(r+1, c, result+1);
    if((c > 0) && !visit[r][c-1] && !alphabet[map[r][c-1]-'A'])       DFS(r, c-1, result+1);
    if((c < C-1) && !visit[r][c+1] && !alphabet[map[r][c+1]-'A'])     DFS(r, c+1, result+1);
    visit[r][c] = false;
    alphabet[map[r][c]-'A'] = false;
}

int main(void)
{
    string str;
    cin>>R>>C;
    for(int i=0; i<R; i++) {
        cin>>str;
        for(int j=0; j<C; j++) {
            map[i][j] = str[j];
        }
    }
    DFS(0,0,1);
    cout<<maximumcount<<endl;
    return 0;
}

풀이

백트래킹에 대해 조금씩 이해가 되고있다.
이전 문제들보다 더 어려운 경우였는데, 이번에는 '이전 내용을 지워줘야 하는' 문제였다.
사실 그 기준을 명확하게 구별하려면 생각이 좀 더 깊이 있어야 할 것 같은데..
이전에 DFS를 이용한 최단거리 푸는 문제같은 형식같기도 하면서 아닌 것 같다.
각 경우에 따라서 내가 이동하고자 하는 곳의 알파벳의 유무와 방문유무를 확인해서 모두를 만족하면 그 방향으로 이동한다.
단, 이후에 그 곳을 또 방문하게 되는 녀석이 존재할 수 있으므로, 그 녀석을 위해 방문하지 않았다고 판단할 수 있도록 초기화해주는 작업이 필요하다.

내가 궁금한 것은 재귀과정을 겪으면서 그 '초기화'의 과정이 언제까지 남느냐이다.
그림으로 좀 해결을 해봐야할 것 같은데...

백트래킹이 이해안가면 테스트로 만들어놓은 이곳 참조해보자