백준 알고리즘 1987번 알파벳 C언어

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R,C<=20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

문제 풀이

1. 처음 map을 입력받을 때에 char로 받을지, 아니면 알파벳의 아스키코드 int 값으로 받아올지 고민했다. 

int 값으로 받으니 뭐가 이상하게 받아지는데 그거는 char로 입력받으면서 \n 값도 같이 읽어서 그런 것이었다.

그건 scanf(" %c", &map[i][j]); 이렇게 %c 앞에 한 칸 띄우고 받았더니 해결할 수 있었다.

 

2. visited 는 방문 여부를 확인하는 것.

 

3. alphabet_check는 받아온 대문자의 아스키 코드 값에 'A'를 빼서 알파벳의 인덱스 번호를 받았다.

A는 0, B는 1, C는 2 ....  이렇게 받아와서 해당 알파벳 칸에 방문했으면 alphabet_check[] =1을 하여 같은 알파벳이 적힌 칸을 두 번 지나가지 않도록 하였다. 

 

4. 여기서는 백트래킹 기법이 필요하다. 처음에는 이해하기 힘들었는데 어느 분이 블로그에 친절하게 예시를 들어주셔서 알 수 있었다.

https://pangsblog.tistory.com/33 

[백준-1987]-[DFS-백트래킹]-알파벳

 

5. 백트래킹을 하는 경우에는 가중치?같은 값을 바로 확인하기가 어려운 것 같다.

예를 들어서 이 문제 같은 경우에는 총 최대 이동 칸 갯수를 구하는 것인데 백트래킹이 진행되므로 값이 계속 변할 것이다.

그래서 항상 백트래킹이 들어가는 dfs 문제 같은 경우에는 dfs 함수를  시작하기에 앞서 if 문으로 해당 값이 최소인지 최대인지 확인한다.

value 값이 현재 말이 지나온 칸의 개수를 의미한다.

 

#include<stdio.h>
#define SZ 21
 
int R; int C;
int map[SZ][SZ];
int move_cnt = 1;
 
int visited[SZ][SZ] = { 0 };
int alphabet_check[27] = { 0 };
 
int vectX[4] = { 0, 0, 1, -1 };
int vectY[4] = { 1, -1, 0, 0 };
 
 
void do_dfs(int a, int b, int value) {
    int nextX; int nextY;
    if (value > move_cnt) {
        move_cnt = value;
    }
 
    for (int i = 0; i < 4; i++) {
        nextX = a + vectX[i];
        nextY = b + vectY[i];
 
        if (nextX >= 1 && nextY >= 1 && nextX <= R && nextY <= C) {
            if (alphabet_check[map[nextX][nextY]-'A'] == 0 && visited[nextX][nextY]==0) {
                visited[nextX][nextY] = 1;
                alphabet_check[map[nextX][nextY] - 'A'] = 1;
                do_dfs(nextX, nextY, value + 1);
                alphabet_check[map[nextX][nextY] - 'A'] = 0;
                visited[nextX][nextY] = 0;
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &R, &C);
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            scanf(" %c", &map[i][j]);
        }
    }
 
    alphabet_check[map[1][1] - 'A'] = 1;
    visited[1][1] = 1;
    do_dfs(1, 1, 1);
 
    printf("%d", move_cnt);
}