백준 1987 : 알파벳

문제 링크입니다 https://www.acmicpc.net/problem/1987

1987번: 알파벳

입력으로 주어지는 세로 R칸, 가로 C칸인 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀있고, 1행 1열에는 말이 놓여 있습니다. 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는 말이 지금까지 지나온 알파벳은 지날 수 없을 때, 지날 수 있는 최대 칸 수를 구하는 문제였습니다. DFS를 통해 문제를 해결할 수 있었고, 자세한 건 주석 참고해주세요!

 

 

[소스코드]

 

#include<cstdio>
 
bool check[50]; // 방문한 알파벳을 처리해줄 check 배열
int r, c, map[25][25], ans;
 
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,-1,0,1 };
 
// (y, x)부터 시작해서 상하좌우로 인접한 칸에 아직 방문하지 않은 알파벳이라면
// 방문하고 방문할 때 마다 cnt 값을 증가시키며 cnt의 최댓값을 ans에 저장해주는 함수
void do_dfs(int y, int x, int cnt) {
 
    // 방문한 칸의 개수를 update 합니다
    if (ans < cnt) ans = cnt;
 
    // 상하좌우 네 방향을 탐색합니다
    for (int i = 0; i < 4; i++) {
 
        // 다음 칸을 결정하고
        int yy = y + dy[i], xx = x + dx[i];
 
        // 그 칸이 배열을 벗어났거나 이미 방문했던 알파벳이 들어있는 칸이라면
        // 다시 올라가서 for문을 돕니다
        if (yy < 0 || yy >= r || xx < 0 || xx >= c || check[map[yy][xx]]) {
            continue;
        }
 
        // 방문했던 적이 없는 알파벳이 있는 칸이고, 배열 범위 내부라면
        // 해당 알파벳을 방문처리해주고 cnt를 하나 늘리고 
        // 다음칸을 찾으러 갑니다
        check[map[yy][xx]] = true;
        do_dfs(yy, xx, cnt + 1);
 
        // 모든 경우 탐색을 위해 dfs가 할 수 있는 일을 다 했으면
        // 해당 칸을 미방문 처리 해주고 다른 칸을 탐색합니다
        check[map[yy][xx]] = false; 
    }
}
 
int main(void) {
 
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) {
            char x;
            scanf(" %c", &x);
            map[i][j] = x - 'A' + 1;  // 애초에 입력을 숫자로 바꿔서 받습니다
        }
 
    // (0, 0)에 있는 알파벳은 방문처리하고
    check[map[0][0]] = true;
 
    // dfs 함수를 호출하는데, (0, 0)은 방문했으므로 cnt 값은 1로 줍니다
    do_dfs(0, 0, 1);
    printf("%d", ans);
    return 0;
}