[백준/BOJ] 17244 아맞다우산 - 접근과 풀이 (c++)

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

17244번: 아맞다우산

비트마스킹에 빠져있을 때 푼 문제. 

 

싸지방에서 풀이 올리던 블로그에서 가져온 글 - 2

 

---

접근 방법

 

4991번 문제 풀이 에서 언급했던 것 처럼 배열에서 최소길이와 특정 지점을 모두 방문해야하고, 중복 방문이 허용되므로 5개의 지점의 방문 상태를 비트마스킹으로 나타내서 푼다. 아주 전형적인 bfs + bitmasking 문제.

 

---

풀이

 

tag : dfs, bitmasking

//BOJ 17244
#include <iostream>
#include<string.h>
#include<queue>
#include<utility>
#define piii pair<pair<int,int>,int>
#define mp make_pair
using namespace std;
int N,M;
int cnt=0;
char arr[51][51];
int v[1<<5][51][51];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int solve(int r,int c){
  int d=0;
  queue<piii> q;
  q.push(mp(mp(r,c),0));
  v[0][r][c]=1;
  while(!q.empty()){
    int qs=q.size();
    for(int s=0;s<qs;s++){
      piii deq=q.front();
      q.pop();
      if(arr[deq.first.first][deq.first.second]=='E' 
        && deq.second==((1<<cnt)-1)) return d;
      for(int i=0;i<4;i++){
        int nr=deq.first.first+dy[i];
        int nc=deq.first.second+dx[i];
        int bit=deq.second;
        if(nr<0 || nc<0 || nr>=N || nc>=M) continue;
        if(arr[nr][nc]=='#' || v[bit][nr][nc]!=0) continue; //벽 or 방문
        if(arr[nr][nc]>='0' && arr[nr][nc]<='4')
          bit=bit | (1<<(arr[nr][nc]-'0'));
        q.push(mp(mp(nr,nc),bit));
        v[bit][nr][nc]=1;
      }
    }
    d++;
  }
  return 987654321;
}
int main() {
  char obj='0';
  int sy,sx;
  cin>>M>>N;
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin>>arr[i][j];
      if(arr[i][j]=='X')
        arr[i][j]=obj++,cnt++;
      else if(arr[i][j]=='S')
        sy=i,sx=j;
    }
  }
  
  memset(v,0,sizeof(v));
  cout<<solve(sy,sx);
  
}