[4991] 로봇 청소기

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

로봇 청소기의 시작위치와 로봇 청소기가 치워야 할 쓰레기들의 위치가 주어졌을 때

로봇이 모든 쓰레기들을 치우는데 필요한 최소 움직임을 출력하는 문제이다.

BFS를 이용해 로봇 청소기와 각 쓰레기들 간의 거리를 모두 계산 후

next_permutation을 이용해 모든 수열에 대해 값을 더해보고 최솟 값을 출력해 주었다.

사실 next_permutation말고 DP를 이용해도 가능한데 쓰레기의 최대 개수가 10개 밖에 되지 않아서

그냥 완탐으로 구현했다.

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int arr[22][22];
int len[11][11];
bool visit[22][22];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m;
int dirtysize;
 
bool isPoosible(int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n;
}
 
void bfs(int x, int y) {
    queue<pair<int, int> > qu;
    int cnt = 0;
    visit[x][y] = 1;
    qu.push({ x, y });
    while (int s = (int)qu.size()) {
        while (s--) {
            int cx = qu.front().first;
            int cy = qu.front().second;
            qu.pop();
            if (arr[cx][cy] >= 0) len[arr[x][y]][arr[cx][cy]] = cnt;
            
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + cx;
                int ny = dy[i] + cy;
                if (isPoosible(nx, ny) && arr[nx][ny] != -2 && !visit[nx][ny]) {
                    visit[nx][ny] = 1;
                    qu.push({ nx, ny });
                }
            }
        }
        cnt++;
    }
}
 
int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        if (!n && !m) return 0;
        memset(arr, 0, sizeof(arr));
        memset(len, 0, sizeof(len));
        int cnt = 1;
        queue<pair<int, int> > dirty;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <n; j++) {
                char c;
                scanf(" %1c", &c);
                if (c == 'o') {
                    arr[i][j] = 0;
                    dirty.push({ i, j });
                }
                else if (c == '.') arr[i][j] = -1;
                else if (c == 'x') arr[i][j] = -2;
                else {
                    arr[i][j] = cnt++;
                    dirty.push({ i, j });
                }
            }
        }
 
        dirtysize = (int)dirty.size();
        for (int i = 0; i < dirtysize; i++) {
            memset(visit, 0, sizeof(visit));
            int x = dirty.front().first;
            int y = dirty.front().second;
            dirty.pop();
            bfs(x, y);
        }
        
        if (dirtysize == 1) {
            puts("0");
            continue;
        }
        vector<int> vt;
        for (int i = 1; i < dirtysize; i++) vt.push_back(i);
        int mini = 987654321;
        bool flag = 0;
        do {
            int sum = len[0][vt[0]];
            if (sum == 0) flag = 1;
            for (int i = 0; i < dirtysize - 2; i++) {
                sum += len[vt[i]][vt[i + 1]];
                if (len[vt[i]][vt[i + 1]] == 0) flag = 1;
            }
            mini = min(mini, sum);
        } while (next_permutation(vt.begin(), vt.end()));
        if (flag) puts("-1");
        else printf("%d\n", mini);
    }
    return 0;
}