[C언어] 백준 1987 : 알파벳

백준 1987 : 알파벳

 

문제 링크

www.acmicpc.net/problem/1987

1987번: 알파벳

 

 

문제 내용

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

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

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

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

 

 

Idea

원래 dfs 알고리즘을 짤 때 방문 기록인 visit을 만들어서 사용했었는데 이번 문제의 방문 조건은 알파벳의 중복이기 때문에 26개의 인덱스를 가지는 alpha 배열을 만들어 주었다.

 

또한, 지나온 길의 칸을 계산해주기 위해 매개변수로 cnt를 추가하여 매번 dfs를 호출할때마다 이 cnt를 비교하여 최대 칸 수를 비교해준다.

 

그리고 방문이 끝나면 해당 알파벳의 방문기록을 해제시켜준다.

(골드 4 문제 치고는 쉬운편인듯)

 

끝! 자세한 내용은 아래 코드로!

 

 

Code

#include <stdio.h>
#define MAX(a,b) a>b?a:b
 
int alpha[26];
int table[20][20];
int result;
int r, c;
 
void dfs(int x, int y, int cnt) {
 
    //알파벳 체크해주고 탐색 개수 검사
    alpha[table[x][y]] = 1;
    result = MAX(result, cnt);
 
    int dx[] = { 1,-1,0,0 };
    int dy[] = { 0,0,1,-1 };
 
    //상하좌우 이동
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        //조건에 맞다면 방문, 방문이 끝나면 기록 해제
        if (nx >= 0 && ny >= 0 && nx < r && ny < c && !alpha[table[nx][ny]]) {
            dfs(nx, ny, cnt + 1);
            alpha[table[nx][ny]] = 0;
        }
    }
}
 
int main() {
    char str[25];
    scanf("%d %d", &r, &c);
 
    //보드 입력
    for (int i = 0; i < r; i++) {
        scanf("%s", str);
        for (int j = 0; j < c; j++) {
            table[i][j] = str[j] - 'A';
        }
    }
 
    //dfs, 좌측 상단 검사
    dfs(0, 0, 1);
 
    //결과 출력
    printf("%d\n", result);
    return 0;
}