[백준/BOJ] 4991 로봇청소기 - 접근과 풀이 (c++)

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

4991번: 로봇 청소기

kks227 블로그 따라가며 알고리즘 다시 익히는 중이다. 비트마스킹을 되게 재밌게 했었는데 기억이 안나서 감잡기 문제.

 

---

접근 방법

 

딱 봐서 bfs문제인데, 방문했던 칸을 다시 방문할 수 있다는 조건이 존재한다. 1194번 문제랑 비슷하게, 현재 방문한 상태를 저장하는 변수 하나를 큐에 같이 넣어서 탐색하면 된다. 

 

'n*m 배열의 최단거리' + '특정 지점 모두 방문'  두 조건이 붙으면 bfs+비트마스킹으로 푸는 정석인 것 같음.

 

청소할 곳이 10개밖에 안되므로 1<<10 * 20 * 20 크기의 visited 배열을 사용하므로 메모리도 문제없다. 

 

---

풀이

 

tag : bfs, bitmasking

 

#include<iostream>
#include<queue>
#include<utility>
#include<string.h>

using namespace std;
const int dy[4]={-1,0,1,0};
const int dx[4]={0,1,0,-1};
int w,h;
char arr[21][21];
int visited[1<<10][21][21];
int cnt=0;

typedef struct info{
  int bit;
  int r;
  int c;
}info;

int bfs(int r,int c){
  int depth=0;
  info initInfo = {0,r,c};
  queue<info> q;
  q.push(initInfo);
  visited[0][r][c]=1;

  while(!q.empty()){
    int qs=q.size();
    for(int i=0;i<qs;i++){
      info deq=q.front();
      q.pop();
      if(deq.bit== (1<<cnt) -1){
        return depth;
      }
      for(int j=0;j<4;j++){
        int nr=deq.r+dy[j];
        int nc=deq.c+dx[j];
        if(nr<0 || nc<0 || nr>=h | nc>=w || arr[nr][nc]=='x')
          continue;
        if(visited[deq.bit][nr][nc]==1) //현재 단계에서 방문
          continue;
        char dest = arr[nr][nc];
    
        info newInfo;
        if(dest>=0 && dest<=9){ //더러운곳 

          /*
          if(deq.bit & 1<<dest) //지금까지 방문한 더러운곳은 갈필요 없다
            continue;           //방문한 더러운곳을 다시 되돌아가는경우가있음.
          */

          //방문한적없는 더러운곳
          newInfo = {deq.bit | 1<<dest, nr, nc};
        }
        else { //방문한적없는 일반 땅
          newInfo = {deq.bit, nr, nc};
        }
        q.push(newInfo);
        visited[newInfo.bit][newInfo.r][newInfo.c]=1;
      }
    }
    depth++;
  }
  return -1;
}

int main(){
  int sr,sc;
  while(1){
    cnt=0;
    cin>>w>>h;
    if(!w)
      return 0;
    
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cin>>arr[i][j];
        if(arr[i][j]=='o')
          sr=i,sc=j;
        if(arr[i][j]=='*')
          arr[i][j]=cnt++;
      }
    }
    memset(visited,0,sizeof(visited));
    cout<<bfs(sr,sc)<<endl; 
  }
}

 

코드 중간에 /*  */ 주석으로 처리한 부분때문에 30분정도 반례를 뒤졌다. 

더러운 곳을 방문할 때 이미 청소한 곳이어도 지나갈 수 있는데, 지나가지 못하게 했다..조심