백준)1987-알파벳

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

1987번: 알파벳

문제

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

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

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

입력

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

출력

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

-----------------------------------------------------------------------------------------------------------------------------------

풀이

알파벳 대문자 를 입력받으므로 방문 유무 배열을 visited 배열을 [ 91 ]로 선언한다 (아스키코드 값 기준 A : 65 ~ Z : 90)

다음 배열 전체를 탐색해야 하므로 BFS 퍼져가는 문제 스타일로 해결해준다. 매 순회하면서 Max < cnt 이면

Max 값을 경신해주는 방법으로 최대 값을 찾아준다. 

map 배열 타입이 char  이므로 visited 배열에 넣을떄  int로 캐스팅해준다. 

-----------------------------------------------------------------------------------------------------------------------------------

#include<iostream>
using namespace std;
 
int R,C;
 
char map[21][21];
char visited[91];
 
int vety[]={0,1,0,-1};
int vetx[]={1,0,-1,0};
int Max;
 
void dfs(int y, int x , int cnt)
{
    int i, nextx ,nexty;
    
    for(i=0 ; i<4; i++)
    {
        nexty = y + vety[i];
        nextx = x + vetx[i];
        
        if( visited[ map[nexty][nextx] ] )
        {
            if(Max < cnt)
                Max = cnt;
            continue;
        }
        
        
        if(nextx >= 0 && nextx <C && nexty >=0 && nexty <R)
        {
            
            visited[ (int)map[nexty][nextx]  ] = 1;
                dfs(nexty ,nextx , cnt+1);
            visited[(int)map[nexty][nextx]   ] = 0;
            
            
        }
        
    }
    
}
 
 
 
 
 
int main()
{
    int i,j;
    
    cin >> R >> C;
    
    for(i=0 ; i< R; i++ )
        cin >> map[i];
    
    visited[ (int)map[0][0] ] = 1;
    
    dfs( 0, 0 ,1 );
    
    cout << Max;
    
    
    
    
    
    return 0; 
}