백준 1987 - 알파벳 - DFS

문제

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

풀이전략

1. 시간은 2초로 매우 충분하다. 따라서 시간 공간 제약없이 문제를 해결 할 수 있다.
2. 같은 알파벳이 적힌 칸을 두번 지날 수는 없다. 즉 알파벳은 총 26개이므로 26개의 체크배열을 만들어서 값을 체크해준다.
3. 가장 긴 경로를 찾는 것이므로 DFS로 해결해 준다.

코드

#include<bits/stdc++.h>

using namespace std;

int R, C;
char a[22][22];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
//알파벳 26개의 체크배열
bool ch[26];
int res = 1, cnt = 1;
// 모든 값의 upperA에 해당하는 int값을 빼주면 배열의 index로 0부터 순차적으로 넣을 수 있다. 
const int upperA = 65;
void DFS(int r, int c){
    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];
        /// 주의할부분 지금까지와는 조건이 다르므로 a[rr][cc] >= upperA 라는 조건이 필요함.
        if( !ch[a[rr][cc]-upperA] && (a[rr][cc] >= upperA)){
            ch[a[rr][cc]-upperA] = true;
            cnt++;
            DFS(rr, cc);
            if(cnt > res) res = cnt;
            ch[a[rr][cc]-upperA] = false;
            cnt--;            
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> R >> C;
    for(int i = 1; i<=R; i++){
        for(int j=1; j<=C; j++){
            cin >> a[i][j];
        }
    }
    memset(ch, false, sizeof(ch));
    ch[a[1][1]-upperA] = true;
    DFS(1, 1);
    // cout<<(int)'A'<<endl; // 65
    // cout<<0 - upperA << endl;
    cout<<res<<endl;
    return 0;
}

소감

이 문제를 풀며 a[rr][cc] >= upperA라는 조건이 매우 중요했다. 나는 이런 상하좌우를 확인하는 문제를 해결할때 주로 배열의 사이즈를 더 크게 만들어 0보다 작은 index 등의 배열보다 더 큰 값을 접근하는 것을 방지하는데 문제에서 ch를 체크할때 우리가 구해야할 영역이 아닌 다른 부분은 다 false로 초기화 되어있기 때문에 이를 방지하지 않으면 구해야할 영역이 아닌 다른 부분도 구할 수 있기 때문이다.