[ 백준 ] 1194번 - 달이 차오른다, 가자. ( C++ )

bfs 문제인데, 조금 응용이 필요한 문제였다.

풀이를 고민하다가 두가지 의문이 풀리지 않아서 다른 사람의 풀이를 참고하여 풀었다.

다음에 비슷한 유형의 문제에서는 잘 풀 수 있었으면 좋겠다.

 

 

<문제>

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

1194번: 달이 차오른다, 가자.

 

 

<참고해서 푼 풀이>

위에서 말한대로 풀지 못했던 두 가지 의문을 다음과 같이 풀었다.

 

1) 이 문제는 지금껏 풀었던 문제와 다르게 방문했던 곳을 다시 방문할 수도 있다. 열쇠를 구하러 갔다가 다시 방문할 수 있기 때문이다. 이걸 어떻게 풀어야할까?

-> 방문 체크 배열을 3차원 배열로 사용하자. visited[x][y][key]와 같이 열쇠 상태에 따라 방문을 체크하도록 하면 된다.

 

2) 6개의 열쇠 소유 여부를 어떻게 관리할까? 

-> 비트 마스킹 기법을 사용하면 된다! 생각보다 비트 마스킹을 사용하면 수월할 때가 많으니까 잘 활용해야겠다. a~f의 6개 열쇠여부를 나타내도록 이진수로 표현하면 000000 ~ 111111 이다. 즉, 0에서 63까지이다. 배열로 표현하기에도 좋다. 

 

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

struct node{
  int x,y;
  int key;
  int time;
};

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  int n,m;
  cin>>n>>m;
  char maze[50][50];
  bool visited[50][50][64] = {false,};
  int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
  queue<node> q;
  
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin>>maze[i][j];
      if(maze[i][j] == '0'){
        node start;
        start.x = i;
        start.y = j;
        start.key = 0;
        start.time = 0;
        q.push(start);
      }
    }
  }
  
  while(!q.empty()){
    int x = q.front().x;
    int y = q.front().y;
    int key = q.front().key;
    int time = q.front().time; q.pop();
    
    if(maze[x][y] == '1'){
      cout<<time;
      return 0;
    }
    
    for(int i=0; i<4; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      
      if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
      if(maze[nx][ny] == '#') continue;
      
      //열쇠 
      if(maze[nx][ny]>='a' && maze[nx][ny]<='f'){
        int nkey = key | (1 << (maze[nx][ny] - 'a'));
        
        if(visited[nx][ny][nkey]) continue;
        node next;
        next.x = nx;
        next.y = ny;
        next.time = time + 1;
        next.key = nkey;
        
        q.push(next);
        visited[nx][ny][nkey] = true;
      }
      
      //문
      else if(maze[nx][ny]>='A' && maze[nx][ny]<='Z'){
        int check = key & (1 << (maze[nx][ny] - 'A'));
        
        if(check == 0 || visited[nx][ny][key]) continue;    
        node next;
        next.x = nx;
        next.y = ny;
        next.time = time + 1;
        next.key = key;
        
        q.push(next);
        visited[nx][ny][key] = true;
      }
      
      else if(!visited[nx][ny][key]){
        node next;
        next.x = nx;
        next.y = ny;
        next.time = time + 1;
        next.key = key;
        q.push(next);
        visited[nx][ny][key] = true;
      } 
    }
  }
  cout<<-1;
}