[백준] 1987 알파벳

DFS+비트마스크를 이용해 풀 수 있다

이미 지나간 알파벳을 지나갈 수 없으므로 비트를 이용해 확인하자

DFS를 돌리며 비트를 이용해 확인하고 지나갈 때 추가하면 쉽게 답을찾을 수 있다!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n,m,ans;
char map[22][22];
bool check[22][22];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
 
void dfs(int x,int y,int alpha,int dist){
    int num = map[x][y]-'A';
    if(alpha&(1<<num)) return;
     
    check[x][y]=true;
    alpha|=(1<<num);
 
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(0<=nx && nx <n && 0<=ny && ny <m){
            if(!check[nx][ny]) dfs(nx,ny,alpha,dist+1);
        }
    }
    check[x][y]=false;
    ans = max(ans,dist);
}
 
int main(){
    freopen("input.txt","r",stdin);
    scanf(" %d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf(" %1c",&map[i][j]);
        }
    }
    dfs(0,0,0,1);
    printf("%d\n",ans);
}