알파벳 C++ - 백준 1987

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

백트래킹 문제.

문제 접근

$i$번째 알파벳까지 왔을 때 어떤 알파벳이 사용되었는지 확인하기 위해

bool 배열을 파라미터로 받아주었다.

(vector로 돌리면 TLE난다.)

$(0,0)$부터 시작해서 백트래킹을 돌려주었다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int r,c;
char f[20][20];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int ans=1;

void solve(int x, int y,int cnt,bool check[26]){
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(r<=nx || nx<0 || c<=ny || ny<0) continue;
        if(check[f[nx][ny]-'A']) continue;
        check[f[nx][ny]-'A']=true;
        cnt++;
        solve(nx,ny,cnt,check);
        check[f[nx][ny]-'A']=false;
        ans=max(ans,cnt);
        cnt--;
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> r >> c;
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) cin >> f[i][j];
    bool arr[26]={0,};
    arr[f[0][0]-'A']=true;
    solve(0,0,1,arr);
    cout << ans;
    return 0;
}