BOJ - 로봇 청소기 (4991)

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

4991번: 로봇 청소기

 

 

오늘 또한 완전탐색입니다.

 

지도가 주어졌을 때 최단거리는 보통 BFS로 구하게 됩니다.

 

하지만, 최대 10개가 주어지는 더러운 칸을 어떤 순서로 방문하는게 최소로 걸릴지에 대해서

사용할 수 있는 알고리즘이 뾰족히 없어 보입니다.

 

그러므로 모든 더러운 칸의 순열을 생각해 볼 수 있습니다.

 

즉, 시간복잡도 O(N!) 이지만 N이 최대 10이므로 10! = 3,628,800‬ 으로 시간안에 충분히 가능합니다.

 

사실 이 문제는 '해밀턴 회로'(모든 정점을 한 번씩 모두 방문하는 경로) 문제로 생각해 볼 수 있습니다.

해밀턴 회로 문제는 NP-Complete에 속하는 문제입니다.

 

이 문제의 풀이를 다음과 같이 생각해 볼 수 있습니다.

 

1. 모든 정점 사이의 거리를 BFS를 통해 구한다.

2. 모든 순열을 만들어 모든 정점을 방문하는데 걸리는 시간 중 최소 값을 출력한다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
int dy[] = { 0,-1,0,1 };
int dx[] = { 1,0,-1,0 };
 
struct tt {
    int y, x;
};
 
int n, m;
char mp[22][22];
bool chk[22][22];
int dist[22][22];
vector<tt> v;
 
bool range(int y, int x) {
    return !(y < 0 || y >= n || x < 0 || x >= m);
}
 
int main() {
    const int INF = 123456789;
 
    while (1) {
        cin >> m >> n;
        
        if (!n && !m) return 0;
 
        for (int i = 0; i < 22; i++)
            for (int j = 0; j < 22; j++)
                dist[i][j] = (i == j ? 0 : INF);        // 인접 행렬을 이용하여 거리를 저장한다. INF 값을 갈 수 없음을 뜻한다
 
        v.clear();
 
        char a = '1';                                    // 더러운 칸을 넘버링 해주기 위한 변수
        v.push_back({ -1,-1 });                            // 굳이 처음에 이런식으로 넣어주는 이유는 시작점을 0번으로 고정시켜 나중에 더 쉽게 코딩해주기 위함이다
        for (int i = 0; i < n; i++) {    
            for (int j = 0; j < m; j++) {
                cin >> mp[i][j];
                if (mp[i][j] == 'o' || mp[i][j] == '*') {    // 시작점 또는 더러운 칸이면 지도에 넘버링을 시도하고, bfs하기 위해 벡터에 푸쉬한다
                    if (mp[i][j] == 'o') {                // 미리 v[0]은 의미없는 값 {-1, -1}이 자리잡고 있으므로, 시작점의 좌표로 다시 수정
                        mp[i][j] = '0';                    // 시작점을 0으로 넘버링
                        v[0].y = i, v[0].x = j;
                    }
                    else {
                        mp[i][j] = a++;                    // 더러운 칸은 임의로 넘버링해준다
                        v.push_back({ i,j });
                    }
                }
            }
        }
 
        for (int i = 0; i < v.size(); i++) {            // 모든 곳으로의 거리를 bfs를 통해 구한다
            int move = 0;                                // 보통 거리 측정을 위해서 struct에 변수 하나를 추가해 주기도 하지만 아래와 같은 방법으로 더 손쉽게 구할 수 있음을 봐두자!!
            memset(chk, 0, sizeof(chk));                // 아래는 모두 보통 bfs와 다를 것이 없으므로 설명은 생략
            queue<tt> q;
            q.push(v[i]);
            chk[v[i].y][v[i].x] = true;                
            while (!q.empty()) {
                int limit = q.size();                    // 현재 큐에 들어있는 수 만큼 pop을 하면 모든 곳에서 한발자국 나아간 것과 같다! (중요)
                move += 1;                                // 왜 이런식으로 짰는지 잘 생각해보자
                while (limit--) {
                    tt f = q.front();
                    q.pop();
 
                    for (int dir = 0; dir < 4; dir++) {
                        int ny = f.y + dy[dir], nx = f.x + dx[dir];
                        if (!range(ny, nx) || mp[ny][nx] == 'x' || chk[ny][nx]) continue;
                        if (mp[ny][nx] != '.') {
                            dist[i][mp[ny][nx] - '0'] = move;    // 더러운칸 또는 시작칸과 만났으므로 거리를 저장
                        }
                        chk[ny][nx] = true;
                        q.push({ ny, nx });
                    }
                }
            }
        }
 
        vector<int> vv;
        for (int i = 0; i < v.size(); i++) vv.push_back(i);        // 각 더러운칸의 방문 순열을 만들어내기 위해 벡터를 만든다 
 
        int ans = INF;                                            // 일단 최댓값으로 답을 세팅 후 답을 구한다
        do {
            int total_dist = 0;
            for (int i = 1; i < vv.size(); i++) {                // vv 에 저장되어 있는 순서로 방문을 한다
                total_dist += dist[vv[i-1]][vv[i]];
            }
            ans = min(ans, total_dist);
        } while (next_permutation(vv.begin() + 1, vv.end()));    // 순열을 구할시 주의사항은 반드시 vv 벡터가 오름차순으로 정렬되어 있어야 한다는 것이다
    
 
        if(ans == INF) cout << -1 << endl;
        else cout << ans << endl;
    }
}