1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
순수하게 DFS(깊이우선탐색)만으로 풀수 있는 문제이며, 아마 가장 흔하게 나오는 깊이우선탐색의 유형일 것 같다. 주의할 점은 탐색을 하면서 이미 한번 지나간 알파벳에 대해서 방문 여부를 관리해야 하는데, 깊이우선 탐색 전에 방문 상태를 true로.. 탐색을 마치고 재귀호출에서 빠져 나왔을때는 다음 경로 계산을 위해 방문 여부 상태를 false로 되돌려 주어야 한다.
#include <stdio.h>
int R, C;
int map[22][22];
bool visited[27];
int dx[4] = {0, +1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int result = 0;
void dfs(int y, int x, int distance){
if(distance > result) {
result = distance;
}
visited[map[y][x]-'A'] = true;
for(int i=0; i<4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if(ny >= 1 && ny <= R && nx >= 1 && nx <= C && visited[map[ny][nx]-'A'] == false){
dfs(ny, nx, distance + 1);
}
}
visited[map[y][x]-'A'] = false;
}
int main () {
scanf("%d%d", &R, &C);
for(int i=1; i<=R; ++i){
char temp[21];
scanf("%s", temp);
for(int j=1; j<=C; ++j){
map[i][j] = temp[j-1];
}
}
visited[map[1][1]-'A'] = true;
dfs(1, 1, 1);
printf("%d\n", result);
return 0;
}