(4991) 로봇 청소기

#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
struct Pair {
    int x, y, v;
    Pair(int x, int y, int v) {
        this->x = x;
        this->y = y;
        this->v = v;
    }
};
class Edge {
public:
    int node[2];
    int value;
    Edge(int x, int y, int v) {
        this->node[0] = x;
        this->node[1] = y;
        this->value = v;
    }
    bool operator<(Edge& edge) {
        return this->value < edge.value;
    }
};
int c, r,sx,sy;
char map[21][21];
int posi[21][21];
bool d[21][21][11];
bool so[15];
int dist[21][21][11];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans=987654321;
 
vector<pair<int, int> > v;
vector<Edge> poe;
int os = 0;
void bfs(int x, int y, int node1) {
    queue<pair<int, int> > q;
    q.push({ x,y });
    d[x][y][node1] = true;
    while (!q.empty()) {
        x = q.front().first; y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; int ny = y + dy[i];
            if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                if (d[nx][ny][node1] == false && map[nx][ny] != 'x') {
                    d[nx][ny][node1] = true;
                    dist[nx][ny][node1] = dist[x][y][node1] + 1;
                    q.push({ nx,ny });
                    if (map[nx][ny] == '*' || map[nx][ny] == 'o') {
                        poe.push_back(Edge(node1, posi[nx][ny], dist[nx][ny][node1]));
                        os++;
                    }
                }
            }
        }
    }
}
 
 
void dfs(int x,int start, int point, int cnt,int sum) {
    if (ans < sum) return;
    if (cnt == point-1) {
        //cout << "HELLO" << endl;
        if (ans > sum) ans = sum;
        return;
    }
    else {
        //cout << x << '\n';
        for (int i = 0; i < poe.size(); i++) {
            if (poe[i].node[1] == start) continue;
            if(poe[i].node[0] == x){
                if (so[poe[i].node[1]] == false) {
                    so[poe[i].node[1]] = true;
                    dfs(poe[i].node[1], start, point, cnt + 1, sum + poe[i].value);
                    so[poe[i].node[1]] = false;
                }
            }
        }
    }
    
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (true) {
        cin >> c >> r;
        if (c == 0 && r == 0) break;
        ans = 987654321;
        int point = 2;
        v.clear();
        poe.clear();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                cin >> map[i][j];
                if (map[i][j] == 'o') {
                    posi[i][j] = 1;
                    sx = i; sy = j;
                }if (map[i][j] == '*') {
                    posi[i][j] = point;
                    v.push_back({ i,j });
                    point++;
                }
            }
        }
        os = 1;
        bfs(sx, sy, posi[sx][sy]);
        if (os != point - 1)
            cout << -1 << '\n';
        else {
            for (int i = 0; i < v.size(); i++) {
                bfs(v[i].first, v[i].second, posi[v[i].first][v[i].second]);
            }
            so[1] = true;
            dfs(1, 1, point, 1, 0);
            cout << ans << '\n';
            
        }
        
            
        memset(so, false, sizeof(so));
        memset(dist, 0, sizeof(dist));
        memset(d, false, sizeof(d));
 
 
    }
}

처음에, 최소스패닝 트리를써도 괜찮은 문제라고 생각했다.

하지만, 최소경로로 잇고나서, 다시 돌아오는길을 선택할수 없기에, 왔다가 갔다가 하는 행위를 할수없었고,

최소스패닝 트리를 쓰는 문제가 아닌 완전탐색 문제다.