Baekjoon 4991번 로봇 청소기

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int w, h;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int adj[11][11];
int room[20][20];
int visited[20][20];
vector<pair<int, int>> dirty;

bool bfs(int v){
    memset(visited, -1, sizeof(visited));
    int y = dirty[v].first;
    int x = dirty[v].second;
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    visited[y][x] = 0;
    int depth = 0;
    while(!q.empty()){
        depth++;
        int size = q.size();
        for(int i = 0; i < size; i++){
            int cy = q.front().first;
            int cx = q.front().second;
            q.pop();
            for(int j = 0; j < 4; j++){
                int ny = cy+dy[j];
                int nx = cx+dx[j];
                if(0 <= ny && ny < h && 0 <= nx && nx < w){
                    if(visited[ny][nx] != -1) continue;
                    if(room[ny][nx] == 1) continue;
                    q.push(make_pair(ny, nx));
                    visited[ny][nx] = depth;
                }
            }
        }
    }
    for(int u = 0; u < dirty.size(); u++){
        int cy = dirty[u].first;
        int cx = dirty[u].second;
        if(visited[cy][cx] == -1) return false;
        adj[v][u] = visited[cy][cx];
    }
    return true;
}

int solve(vector<int>& path, vector<int>& visited, int currentLength){
    // 기저 사례
    if(path.size() == dirty.size())
        return currentLength;
    // 재귀 호출
    int ret = INF;
    for(int next = 0; next < dirty.size(); next++){
        if(visited[next]) continue;
        visited[next] = 1;
        int here = path.back();
        path.push_back(next);
        int cand = solve(path, visited, currentLength + adj[here][next]);
        ret = min(ret, cand);
        visited[next] = 0;
        path.pop_back();
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while(true){
        cin >> w >> h;
        if(w == 0 && h == 0) break;
        dirty.clear();
        char tmp;
        int robot;
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                cin >> tmp;
                // 0 : floor, 1 : furniture
                if(tmp == 'x') room[y][x] = 1;
                else room[y][x] = 0;
                // 로봇 청소기의 위치도 더러운 칸으로 취급
                if(tmp == 'o') robot = dirty.size();
                if(tmp == 'o' || tmp == '*') dirty.push_back(make_pair(y, x));
            }
        }
        bool clean = true;
        for(int i = 0; i < dirty.size(); i++){
            if(!bfs(i)){
                clean = false;
                break;
            }
        }
        if(!clean){
            cout << -1 << "\n";
            continue;
        }
        vector<int> visited(dirty.size());
        vector<int> path;
        visited[robot] = 1;
        path.push_back(robot);
        cout << solve(path, visited, 0) << "\n";
    }
    return 0;
}

로봇 청소기와 더러운 칸들 사이의 최단 거리를 모두 구해두고, 로봇청소기의 위치에서 시작하여 모든 더러운 칸을 지나는 최단 경로를 완전탐색으로 구하였다.

각 테스트 케이스마다 2차원 벡터를 resize 하여 사용했는데 입력한 값과 다르게 초기화되는 원인모를 문제가 있었다.