백준 4991 - 로봇 청소기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

비트마스킹과 BFS를 이용해 풀 수 있는 문제입니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M;
char map[21][21];
int check[21][21][1 << 10];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<P> dust;
P start;

int find_dust(int x, int y){
    for(int i = 0; i < dust.size(); i++){
        if(x == dust[i].F && y == dust[i].S) return i;
    }
}

int bfs(){
    memset(check, 0, sizeof(check));
    queue<pair<pair<int, int>, int>> q;
    q.push({{start}, 0});
    check[start.F][start.S][0] = 1;
    int ret = 0;
    while(!q.empty()){
        int qsize = q.size();
        while(qsize--){
            int x = q.front().F.F;
            int y = q.front().F.S;
            int visit = q.front().S;
            q.pop();
            if(visit == (1 << dust.size()) - 1) return ret;
            for(int i = 0; i < 4; i++){
                int xx = x + dx[i];
                int yy = y + dy[i];
                int n_visit = visit;
                if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                    if(map[xx][yy] != 'x'){
                        if(map[xx][yy] == '*') n_visit |= 1 << find_dust(xx, yy);
                        if(check[xx][yy][n_visit] == 0){
                            check[xx][yy][n_visit] = 1;
                            q.push({{xx, yy}, n_visit});
                        }
                    }
                }
            }
        }
        ret++;
    }
    return -1;
}

void solve(){
    cout << bfs() << "\n";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    while(1){
        cin >> M >> N;
        if(N == 0 && M == 0) break;
        dust.clear();
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                cin >> map[i][j];
                if(map[i][j] == 'o') start = {i, j};
                else if(map[i][j] == '*'){
                    dust.push_back({i, j});
                }
            }
        }
        solve();
    }
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요