[알고리즘] 백준 1987 알파벳 // 비트마스킹, i번째 비트켜짐확인, vis를 숫자1개로 나타내는 힘

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

* 고민했던 부분

• 비트마스킹 발상하기
  • N이 30미만 -> 비트마스킹 도전 -> vis를 숫자 1개로 나타내보자.
• 알파벳을 숫자로 표현하기
  • A - 'A' =0
  • B-A = 1 
  • C-A = 2
  • ...
  • A를 1로 (1<<0)
  • B를 2로 (1<<1)
  • C롤 4로 표한하면 되겠다! (1<<2)
  • 1을 알파벳-'A'만큼 밀면 현재 비트가 나온다! // (1<< (A-'A'))
• i번째 비트가 켜진것을 확인하기
  • (상태 & 현재비트) !=0 -> i번째 비트는 켜진것. -> already visited

• 주의사항
  • 비트연산에는 항상 괄호를 사용할것!

• 모든 탐색이 끝나고 return 될때 정답갱신하는 부분을 어디에 둘지

* 의사코드

알고리즘: 알파벳 보드에서 중복되지 않는 알파벳으로만 이동하는 최장 경로 찾기

입력:
- R: 보드의 행 개수
- C: 보드의 열 개수
- board[R][C]: 각 칸에 알파벳이 적힌 보드

전역변수:
- answer: 찾은 최장 경로의 길이
- dx[], dy[]: 4방향 이동을 위한 방향 배열

함수 DFS(현재_상태, 현재_y좌표, 현재_x좌표, 현재_레벨):
    1. 현재 위치의 알파벳을 비트마스크에 추가
        - 현재_비트 = 1 << (현재 알파벳 - 'A')
        - 현재_상태 = 현재_상태 | 현재_비트

    2. 4방향 탐색
        각 방향에 대해:
            다음_y = 현재_y + dy[i]
            다음_x = 현재_x + dx[i]
            
            2.1 경계 체크
                만약 다음_y < 0 또는 다음_x < 0 또는 
                   다음_y >= R 또는 다음_x >= C 이면:
                    다음 방향으로 continue
            
            2.2 다음 위치의 알파벳 비트마스크 계산
                다음_비트 = 1 << (다음 알파벳 - 'A')
            
            2.3 방문 여부 체크
                만약 (현재_상태 & 다음_비트) != 0 이면:
                    // 이미 방문한 알파벳이므로
                    다음 방향으로 continue
            
            2.4 다음 위치로 DFS 호출
                DFS(현재_상태, 다음_y, 다음_x, 현재_레벨 + 1)
    
    3. 현재 경로의 탐색이 완료됨
        answer = max(answer, 현재_레벨)
        return

메인 함수:
    1. 입력 받기
        - R, C 입력
        - board 배열에 알파벳 입력
    
    2. DFS 시작
        - DFS(0, 0, 0, 1) 호출
        // 초기 상태 = 0, 시작 위치 = (0,0), 초기 레벨 = 1
    
    3. 결과 출력
        - answer 출력

 

* 전체코드

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

int r,c,ret;
char a[24][24];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};

void dfs(int state, int y, int x, int level) {
    
    int bit = 1<<(a[y][x]-'A');
    state = state | bit;

    // cout<<y<<" "<<x<<" "<<state<<"\n";
    
    for(int i=0;i<4;++i) {
        int ny=y+dy[i];
        int nx=x+dx[i];
        if(ny<0 || nx<0 || ny>=r || nx>=c) continue;
        int nxt_bit = 1<<(a[ny][nx]-'A');
        if((state & nxt_bit) !=0) { // next가 이미 방문했던 곳 인경우
            //비트연산자 우선순위 낮음에 주의!!!
            //==가 먼저 실행되버리는 문제
            continue;
        }
        dfs(state,ny,nx, level+1);
    }

    // 현재 경로에서의 탐색이 완료된 시점에 여기로 옴
    // (더 갈 곳이 없거나, 가능한 모든 경로를 탐색한 경우)
    ret=max(ret,level);
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>r>>c;

    for(int i=0;i<r;++i) {
        for(int j=0;j<c;++j) {
            cin>>a[i][j]; // r,c 아님에 주의!
        }
    }

    dfs(0,0,0,1);

    cout<<ret;
    
    return 0;
}