백준 1987번 : 알파벳 (C++)

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

1987번: 알파벳

 

코드

#include <iostream>
using namespace std;
char arr[20][20];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool alpha[26];
int res,r,c;
void dfs(int x,int y,int num)
{
    num++;
    if(res<num)res=num;
    for(int i=0;i<4;i++)
    {
        if(x+dx[i]>=0 && x+dx[i]<r && y+dy[i]>=0 && y+dy[i]<c)
        {
            if(alpha[arr[x+dx[i]][y+dy[i]]-65]==false)
            {
                alpha[arr[x+dx[i]][y+dy[i]]-65]=true;
                dfs(x+dx[i],y+dy[i],num);
                alpha[arr[x+dx[i]][y+dy[i]]-65]=false;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>r>>c;
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cin>>arr[i][j];
        }
    }
    alpha[arr[0][0]-65]=true;
    dfs(0,0,0);
    cout<<res;
    return 0;
}

 

풀이

 dfs함수를 이용하여 상, 하, 좌, 우의 위치 중에서 (14행) 같은 알파벳이 적힌 칸을 두 번 지날 수 없다는 규칙을 어기지 않는 칸으로 진행한다. (16행) 이를 위해서 alpha 배열을 사용하는데 A-65 =0, Z-65=25이므로 alpha배열의 크기는 26이고 각 알파벳-65의 값이 그 알파벳을 이미 방문했는지 검사하는 인덱스가 된다. (A=0, B=1 ,,,, Z=25) 재귀적으로 진행되는 dfs함수에서 alpha 배열을 이용하기 위해서 18~20행이 코드를 수행한다.