백준 4991 / 로봇 청소기

총 n개의 쓰레기를 치우는 최소거리는

치우는 순서에 따라 다르다.

그렇기에 1,2......, 최대 10번째 쓰레기를 치우는 순서를 모두 정한 후

최소값을 구하면 된다.

총 10!(>300만)개의 경우의수가 생기니 next_permutation 안에서 bfs를 매번 돌리면 시간초과가 뜬다. 

해결법은

로봇청소기와 쓰레기 n개 사이의 거리를 모두 구해놓는 것이다.

쓰레기가 10개라고 가정하면

로봇청소기와 쓰레기 사이의 거리 : 10개

쓰레기와 쓰레기 사이의 거리 : 10C2개

총 55개의 거리를 BFS로 구하면 된다.

코드

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<memory.h>
#include<string>
 
using namespace std;
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1};
 
char map[21][21];
bool check[21][21];
int dist[21][21];
 
int dirtdist[12][12];
 
int h, w;
 
int bfs(int a, int b, int fx, int fy) {
 
    memset(check, false, sizeof(check));
    memset(dist, 0, sizeof(dist));
 
    queue<pair<int, int>>q;
 
    q.push({ a,b });
    check[a][b] = true;
 
    while (!q.empty()) {
        int x = q.front().first;
        int 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 < h && ny >= 0 && ny < w) {
                if (check[nx][ny] == false) {
                    if (map[nx][ny] == '.' || map[nx][ny] == '*' || map[nx][ny]=='o') {
                        check[nx][ny] = true;
                        dist[nx][ny] = dist[x][y] + 1;
                        q.push({ nx,ny });
                    }
                }
            }
        }
    }
 
    return dist[fx][fy];
    
}
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    while (1) {
 
        memset(dirtdist, 0, sizeof(dirtdist));
 
        cin >> w >> h;
 
        if (w == 0 && h == 0) {
            break;
        }
        
        int dirt = 0;
        bool can = true;
        int ssx = 0;
        int ssy = 0;
 
        vector<pair<int, int>>dirtxy;
 
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i][j];
                if (map[i][j] == '*') {
                    dirt++;
                    dirtxy.push_back({ i,j });
                }
                if (map[i][j] == 'o') {
                    ssx = i;
                    ssy = j;
                }
            }
        }
        for (int i = 0; i < dirt; i++) {
 
            int sx = dirtxy[i].first;
            int sy = dirtxy[i].second;
 
            int tmp = bfs(ssx, ssy, sx, sy);
 
            if (tmp == 0) {
                can = false;
                break;
            }
            else {
                dirtdist[11][i] = tmp;
            }
 
            for (int j = i+1; j < dirt; j++) {
            
                if (i != j) {
                    int sx = dirtxy[i].first;
                    int sy = dirtxy[i].second;
                    int fx = dirtxy[j].first;
                    int fy = dirtxy[j].second;
 
                    int tmp = bfs(sx, sy, fx, fy);
            
                    dirtdist[i][j] = tmp;
                    dirtdist[j][i] = tmp;
                }
            }
        }
 
        vector<int>order;
        
        for (int i = 0; i < dirt; i++) {
            order.push_back(i);
        }
 
        int min = -1;
 
        do {
 
            int sx = ssx;
            int sy = ssy;
 
            int ans = 0;
 
            if (can == false || dirt == 0)break;
 
            ans += dirtdist[11][order[0]];
 
            for (int i = 0; i < dirt - 1; i++) {
                ans += dirtdist[order[i]][order[i + 1]];
            }
 
            if (min > ans || min == -1){
                min = ans;
            }
 
        } while (next_permutation(order.begin(), order.end()));
 
        if (dirt == 0) {
            cout << 0 << endl;
        }
        else {
            if (can == false || min == 0) {
                cout << -1 << endl;
            }
            else {
                cout << min << endl;
            }
        }
    }
}