17244 아맞다우산 (비트마스킹)

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

17244번: 아맞다우산

챙겨야 하는 물건의 수가 최대 5개로 작으므로 비트마스크를 사용해 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
int N,M,Bit,idx;
bool vis[53][53][35]; //y x bit
char board[53][53];
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
queue<tuple<int,int,int,int>> Q; //y x cnt bit

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>M; //가로 세로 
	for(int i=0;i<M;i++){
		for(int j=0;j<N;j++){
			cin>>board[i][j];
			if(board[i][j]=='S'){Q.push(make_tuple(i,j,0,0)); vis[i][j][0]=true;}
			if(board[i][j]=='X'){board[i][j]=(idx++)+'0';}
		}
	}
	Bit=(1<<idx)-1;
	//idx는 X의 갯수임
	//X가 4개라면 Bit==15
	//이를 2진수로 바꾸면 1111이므로 한 자리당 X 한 개를 의미한다.
	
	while(!Q.empty()){
		auto cur=Q.front(); Q.pop();
		int curY,curX,curCnt,curBit;
		tie(curY,curX,curCnt,curBit)=cur;
		
		if(board[curY][curX]=='E'&&curBit==Bit){
			cout<<curCnt<<'\n';
			break;
		}
		
		for(int dir=0;dir<4;dir++){
			int ny=curY+dy[dir];
			int nx=curX+dx[dir];
			int nb=curBit;
			if(ny<0||nx<0||ny>=M||nx>=N) continue;
			if(board[ny][nx]=='#') continue;
			
			if(board[ny][nx]>='0' && board[ny][nx]<='4'){nb|=(1<<(board[ny][nx]-'0'));}
			if(vis[ny][nx][nb]) continue;
			vis[ny][nx][nb]=true; Q.push(make_tuple(ny,nx,curCnt+1,nb));
		}
	} 
	return 0;
}

비트마스크를 사용해 문제를 푼 건 이게 처음인데 굉장히 신박한 방식이라고 느꼈다.