4991. 로봇청소기

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

Point

1. 로봇청소기(o)에서 모든 더러운 칸(*)으로 이동하는데 필요한 최소 비용

2. 더러운 칸(*)의 최대 개수는 10개

3. 더러운 칸을 방문하는 순서에 따라 비용이 달라진다.

방문하는 순서에 따라 비용이 달라진다.

쓰레기가 3개인 경우에는 3! = 6가지의 경우의 수가 존재한다.

쓰레기의 최대 개수는 10개이므로 최대 10! =~ 3,600,000 경우의 수가 존재한다.

그렇다면 더러운 칸(*)의 지점을 벡터에 넣고 next_permutation안에서 bfs를 돌리면 어떨까?

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 
 
using namespace std;
int n,m;
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};
int bfs(int n,int m,int y,int x,vector<vector<char>> &area,vector<pair<int,int>>&v)
{
    int sum = 0;
    int starty = y;
    int startx = x;
 
    for(int i=0;i<v.size();i++)
    {   
        vector<vector<int>> visited(n+1,vector<int>(m+1,0));
        vector<vector<bool>> check(n,vector<bool>(m+1,false));
        queue <pair<int,int>> q;
        
        q.push(make_pair(starty,startx));
 
        while(!q.empty())
        {   
            int y = q.front().first;
            int x = q.front().second;
            check[y][x] = true;
 
            q.pop();
 
            if(y==v[i].first && x==v[i].second)
            {   
                starty = y;
                startx = x;
                sum += visited[y-1][x-1];
            }
 
            else
            {
                for(int k=0;k<4;k++)
                {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
 
                    if(ny>=0 && nx>=0 && ny<n && nx<m)
                    {
                        if(area[ny][nx]!='x' && check[ny][nx]==false)
                        {   
                            check[ny][nx]=true;
                            q.push(make_pair(ny,nx));
                            visited[ny][nx] = visited[y][x]+1;
                        }
                    }
                }
            }
        }
 
    }
 
    return sum;
}
int k;
int main()
{
    FASTio;
 
    while(1)
    {
        cin >> m >> n;
        if(n==0 && m==0) break;
        else
        {   
            vector<vector<char>> area(n+1,vector<char>(m+1));
 
            vector<pair<int,int>> v;
            int ans = 999999;
            int y,x;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    cin >> area[i][j];
                    if(area[i][j]=='o')
                    {
                        y = i;
                        x = j;
                    }
                    else if(area[i][j]=='*')
                    {
                        v.push_back(make_pair(i,j));
                    }
                }
            }
            do
            {
                ans = min(ans,bfs(n,m,y,x,area,v));
 
            } while (next_permutation(v.begin(),v.end()));
 
 
            if(ans==0) cout << -1 << endl;
            else cout << ans << endl;
        }
    }
 
    return 0;
}

이렇게하면 next_permutation 안에서 bfs를 수행하기 때문에 O(10! * NM(BFS 수행시간))의 시간이 발생하여 시간초과가 발생한다.

따라서 다음 그림과 같은 방식을 이용하여 문제를 해결했다.

Step 1 . dust_dist[0][1~더러운 칸 수] => 로봇청소기에서 각 더러운칸으로 가는 거리를 BFS로 미리 구한다.

Step 2. dust_dist[i][j]에 i지점에서 j지점으로 가는 거리를 BFS를 통해 미리 구해 놓는다.

Step 3. next_permutation을 통해 dust_dist에 저장된 값을 이용하여 정해진 순서대로 총 거리 계산하여 최소거리를 저장한다.

이렇게 하면 앞선 코드가 O(10! * NM)이 걸렸다면 이 방법에서는 next_permutation을 돌릴 때마다 내부에서 BFS를 수행하는 것이 아니라 미리 거리를 계산해 둔다는 점에서 O(10! + NM)으로 엄청난 시간감소를 볼 수 있다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 
 
using namespace std;
int n,m;
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};
 
int bfs(int n, int m, int y,int x,int desty,int destx,vector<vector<char>>&area)
{
    vector<vector<int>> visited(n+1,vector<int>(m+1,0));
    vector<vector<bool>> check(n+1,vector<bool>(m+1,false));
    check[y][x] = true;
    queue <pair<int,int>> q;
        
    q.push(make_pair(y,x));
 
    while(!q.empty())
    {   
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        if(y==desty && x==destx)
        {   
            break;
        }
        else
        {
            for(int k=0;k<4;k++)
            {
                int ny = y + dy[k];
                int nx = x + dx[k];
 
                if(ny>=0 && nx>=0 && ny<n && nx<m)
                {
                    if(area[ny][nx]!='x' && check[ny][nx]==false)
                    {   
                        check[ny][nx]=true;
                        q.push(make_pair(ny,nx));
                        visited[ny][nx] = visited[y][x]+1;
                    }
                }
            }
        }
    }
 
    return visited[desty][destx];
}
 
int main()
{
    FASTio;
 
    while(1)
    {
        cin >> m >> n;
        if(n==0 && m==0) break;
        else
        {   
            vector<vector<char>> area(n+1,vector<char>(m+1));
            vector<pair<int,int>> v(1);
 
            int ans = -1;
 
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    cin >> area[i][j];
                    if(area[i][j]=='o')
                    {
                        v[0] = make_pair(i,j);
                    }
 
                    else if(area[i][j]=='*')
                    {   
                        v.push_back(make_pair(i,j));
                    }
                }
            }
 
            vector<vector<int>> dust_dist(v.size(),vector<int>(v.size(),0));
 
            // 로봇청소기 -> *까지의 거리 모두 계산해서 저장
            for(int i=1;i<v.size();i++)
            {
                int dist = bfs(n,m,v[0].first,v[0].second,v[i].first,v[i].second,area); 
                dust_dist[0][i] = dist;
            }
        
            // *들 간의 거리
            for(int i=1;i<v.size();i++)
            {
                for(int j=1;j<v.size();j++)
                {
                    dust_dist[i][j] = bfs(n,m,v[i].first,v[i].second,v[j].first,v[j].second,area);
                }
            }
 
            vector<int> order(v.size()-1);
 
            for(int i=0;i<order.size();i++)
            {
                order[i] = i+1;
            }
 
            sort(order.begin(),order.end());
            
            do
            {   
                bool itcant = false;
 
                int sum = dust_dist[0][order[0]];
 
 
                // 첫번째 *로 못가면 다음 조합 살펴보기
                if(sum==0)
                {
                    continue;
                }
 
 
                for(int i=0;i<order.size()-1;i++)
                {   
                    // * -> * 못가면 종료
                    if(dust_dist[order[i]][order[i+1]]==0)
                    {
                        itcant = true;
                        break;
                    }
 
                    // sum에 먼지거리 더해주기
                    sum += dust_dist[order[i]][order[i+1]];
                }    
 
                if(itcant==true)
                {
                    continue;
                }
 
 
                else
                {  
                   
                   if(ans==-1 || ans>sum)
                   {
                   ans = sum;
                   }
                }
 
            } while (next_permutation(order.begin(),order.end()));
 
            cout << ans << endl;
        }
 
    }
 
 
    return 0;
}

문제를 처음 보고 나서는 쉬워보였는데, 풀면서 쉽지 않다는 걸 느꼈다.

처음엔 구현하는 부분에서 생각한 대로 돌아가지 않아 어려웠고 구현 끝에는 시간초과가 발생해서 어떻게 시간을 줄여야 할지 감이 오지 않았다. 구현하는 연습을 많이 해보고, 시간초과를 줄이는 방법에 대해서 많이 고민해봐야겠다...