백준, BOJ, 1987번, 알파벳 : C++ [CPP] ***

음 백트래킹하면서 DFS로 끝까지 가는 것이라 처음 접했을 때는 어려웠다.

 

 

https://www.acmicpc.net/problem/1987

 

---

 

 

#맞는 풀이 ( 백트래킹  + DFS )

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

char arr[20][20];

int alpha[26]; // ASCII 코드 이용하기 'A' = 65  'a'=97

int R,C; //Row(행) , Column(열)

int answer = 0; // 최댓값

//현재 위치, 현재까지의 길이
void dfs(int x, int y, int dist){

    // 최댓값 갱신
    answer = max(dist, answer);

    // 방향조사
    for (int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 범위
        if(nx<0 || nx>= R || ny<0 || ny>= C) continue; //범위
        int temp = (int)arr[nx][ny] - 65;
        if(alpha[temp]) continue; // alpha가 1이면 -> 해당 알파벳을 이미 입력했다면
        
        alpha[temp] = 1; //선택
        dfs(nx,ny,dist+1); //확장
        alpha[temp] = 0; //복원
            
    }
}

int main(){
    
    cin >> R >> C;
    
    //노드 입력
    for(int i = 0; i<R; i++){
        for(int j = 0; j<C; j++){
            cin>>arr[i][j];
        }
    }
    
    
    int num = (int)arr[0][0] - 65; // 해당 문자를 int로 바꿈
    alpha[num] = 1; // 첫번째 문자입력
    dfs(0,0,1);

    
    cout << answer;
    
    return 0;
}