[C/C++] 백준 #1987 알파벳(깊이 우선 탐색)

이번 문제는 깊이 우선 탐색(DFS)를 이용해서 풀었습니다.  백트랙킹과도 같은 기법이긴 합니다.  백트랙킹 자체가 깊이 우선 탐색을 이용하여 푸는 것인만큼 딱히 구분을 지을 필요는 없어보입니다.

 

alphabet

 

갈 수 있는 길이냐 아니냐를 따지기 위해서는 알파벳 마스크(Alphabet mask)를 사용합니다.  일반적인 깊이 우선 탐색은 방문했는지 여부를 따지게 되는 것과는 다릅니다.  알파벳은 오직 한번만 지나갈 수 있기 때문에, 이미 지나온 자리는 다시 방문할 수가 없습니다.  다음으로는 가장 짧은 경로가 아니라 가장 긴 경로를 찾는 것이기 때문에 모든 경로를 다 살펴보아야 합니다.  그러다보면 꽤 많은 경로를 검색하게 됩니다.

 

문제에서 행과 열의 개수가 상당히 적기 때문에 (\( 1 \ge R,~C \ge 20\)), 깊이 우선 탐색을 사용해도 시간초과가 걸리지는 않습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1987
//        - by Aubrey Choi
//        - created at 2019-09-11
//------------------------------------------------
#include <stdio.h>
char map[20][24], mask[26];
int r, c;
int dfs(int y, int x, int s)
{
    int d[4][2]={0,1,1,0,0,-1,-1,0}, max=++s;
    mask[map[y][x]-'A']=1;
    for(int i=0;i<4;i++)
    {
        int ny=y+d[i][0], nx=x+d[i][1];
        if(ny<0||ny>=r||nx<0||nx>=c||mask[map[ny][nx]-'A']) continue;
        int r=dfs(ny, nx, s);
        max=(r>max)?r:max;
    }
    mask[map[y][x]-'A']=0;
    return max;
}
int main()
{
    scanf("%d%d",&r,&c);
    for(int i=0;i<r;i++) scanf("%s", map[i]);
    printf("%d\n", dfs(0,0,0));
}