백준 4991번 - 로봇 청소기

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

4991번: 로봇 청소기

필요한 배경지식

• 1번 풀이 : DFS, BFS
• 2번 풀이 : BFS, 외판원 문제(TSP)
• 3번 풀이 : BFS, DP, 비트마스킹

 

 

문제 해결 방법

방의 크기가 최대 20*20이므로 최단경로를 구하기 위해 BFS를 한번 수행하는 시간은 크게 문제가 되지 않습니다.

더러운 칸의 개수가 10개이므로 BFS를 최대 11번 수행하여 모든 더러운 칸과 로봇청소기 사이의 거리를 어렵지 않게 구할 수 있습니다. (dist 배열)

 

(풀이 1)

우선 최소 이동 횟수를 구하기 위해 완전탐색을 생각해 볼 수 있습니다.

위에서 구한 최단 경로를 이용하여 모든 더러운 칸의 방문 순서를 정하는데에 dfs를 이용한다면 총 개수는 10!이고 이는 충분히 시간안에 들어올 수 있는 풀이입니다.

 

(풀이 2)

모든 더러운 칸과 로봇청소기 시작점 사이의 경로 중 하나라도 방문할 수 없는 경로가 있다면 -1을 출력하면 되지만 모두 방문을 할 수 있다면 위에서 설명한 것 처럼 모든 최단경로를 구해낼 수 있고 이것은 완전그래프로 표현될 수 있습니다. 이때 모든 노드를 방문할 최단 경로를 찾아야 하는데 이러한 문제는 외판원 문제(traveling salesman problem)로 잘 알려져 있습니다. 방문해야 할 노드의 개수가 N개일때 시간복잡도는 O(2^N * N^2)이므로 풀이중 가장 빠른 시간안에 문제를 해결할 수 있습니다.

 

(풀이 3)

방문을 확인하는 배열크기를 늘리고 단순 BFS로 풀어낼 수도 있습니다.

백준에서 풀어볼 수 있는 문제들 중 BFS와 DP 태그가 붙은 최단경로를 구해내는 문제들과 같은 방법입니다.

방문처리하는 배열이 visited[r][c][k] 일때 r과 c는 방의 위치를 의미하며 k는 방문한 더러운 칸의 정보를 비트마스킹으로 표현한 것을 의미합니다. 이렇게 정의하면 로봇이 항상 같은 크기로 이동하므로 단순 BFS로 문제를 간결하게 해결할 수 있습니다.

 

 

1. DFS , BFS 풀이 코드

<hide/>
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using tpi = tuple<int,int,int>;
const int INF = 0x3f3f3f3f;

int N,M,K;
int m[20][20]{};
pii v[11]{};
int dist[11][11]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

bool bfs(int st){
    int vi[20][20]{};
    memset(vi,-1,sizeof(vi));
    queue<tpi> q;
    q.push({0, v[st].xx, v[st].yy});
    vi[v[st].xx][v[st].yy] = 0;

    while(!q.empty()){
        int cd, cy, cx;
        tie(cd, cy, cx) = q.front();
        q.pop();

        for(int i=0; i<4; i++){
            int nd = cd + 1;
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny<0 || nx<0 || ny>=N || nx>=M || vi[ny][nx]!=-1 || m[ny][nx]==-1) continue;
            q.push({nd, ny, nx});
            vi[ny][nx] = nd;
        }
    }

    for(int i=0; i<=K; i++){
        dist[st][i] = vi[v[i].xx][v[i].yy];
        if(dist[st][i] == -1) return false;
    }
    return true;
}

int ans;
bool vi[11]{};
void dfs(int now, int sum, int dpt){
    if(dpt==K){
        ans = min(ans, sum);
        return;
    }

    for(int i=1; i<=K; i++){
        if(vi[i]) continue;
        vi[i] = true;
        sum += dist[now][i];
        dfs(i, sum, dpt+1);
        sum -= dist[now][i];
        vi[i] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(1){
        cin>>M>>N;
        if(!N) break;
        memset(m,-1,sizeof(m));
        K=0;
        string str;
        for(int i=0; i<N; i++){
            cin>>str;
            for(int j=0; j<M; j++){
                if(str[j] == 'o') v[0].xx = i, v[0].yy = j, m[i][j] = 0;
                else if(str[j] == '*') m[i][j] = ++K, v[K].xx = i, v[K].yy = j;
                else if(str[j] == 'x') m[i][j] = -1;
                else m[i][j] = 0;
            }
        }

        bool chk = true;
        for(int i=0; i<=K; i++) {
            if(!bfs(i)) {
                chk = false;
                break;
            }
        }
        if(!chk) { 
            cout<<-1<<'\n';
            continue;
        }
        
        ans = INF;
        dfs(0,0,0);
        cout<<ans<<'\n';
    }
    
}

 

 

 

2. BFS , TSP(바텀업) 풀이 코드

<hide/>
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using tpi = tuple<int,int,int>;
const int INF = 0x3f3f3f3f;

int N,M, K, sty, stx;
int m[20][20]{};
pii v[11]{};
int dp[11][1<<10]{};
int dist[11][11]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

bool bfs(int st){
    int vi[20][20]{};
    memset(vi,-1,sizeof(vi));
    queue<tpi> q;
    q.push({0, v[st].xx, v[st].yy});
    vi[v[st].xx][v[st].yy] = 0;

    while(!q.empty()){
        int cd, cy, cx;
        tie(cd, cy, cx) = q.front();
        q.pop();

        for(int i=0; i<4; i++){
            int nd = cd + 1;
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny<0 || nx<0 || ny>=N || nx>=M || vi[ny][nx]!=-1 || m[ny][nx]==-1) continue;
            q.push({nd, ny, nx});
            vi[ny][nx] = nd;
        }
    }

    for(int i=0; i<=K; i++){
        dist[st][i] = vi[v[i].xx][v[i].yy];
        if(dist[st][i] == -1) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 0;
    while(1){
        tt++;
        cin>>M>>N;
        if(!N) break;
        memset(m,-1,sizeof(m));
        memset(dp,0x3f,sizeof(dp));

        K=0;
        string str;
        for(int i=0; i<N; i++){
            cin>>str;
            for(int j=0; j<M; j++){
                if(str[j] == 'o') v[0].xx = i, v[0].yy = j, m[i][j] = 0;
                else if(str[j] == '*') m[i][j] = ++K, v[K].xx = i, v[K].yy = j;
                else if(str[j] == 'x') m[i][j] = -1;
                else m[i][j] = 0;
            }
        }

        bool chk = true;
        for(int i=0; i<=K; i++) {
            if(!bfs(i)) {
                chk = false;
                break;
            }
        }
        if(!chk) { 
            cout<<-1<<'\n';
            continue;
        }
        
        dp[0][0] = 0;
        for(int mask=1; mask<(1<<K); mask++){
            for(int i=1; i<=K; i++){
                if(mask & (1<<(i-1))) {
                    int pre = mask ^ (1<<(i-1));
                    for(int j=0; j<=K; j++){
                        if(dp[j][pre] >= INF) continue;
                        dp[i][mask] = min(dp[i][mask], dp[j][pre] + dist[j][i]);
                    }
                }
            }
        }

        int res = INF;
        for(int i=1; i<=K; i++){
            res = min(res, dp[i][(1<<K)-1]);
        }
        cout<<res<<'\n';
    }
}

 

 

 

3. BFS + DP(비트마스킹) 풀이 코드

<hide/>
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using dpi = pair<pii,pii>;

int N,M;
int m[20][20]{};
bool vi[20][20][1<<10]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

int bfs(int sty, int stx, int K){
    memset(vi,0,sizeof(vi));
    queue<dpi> q;
    q.push({{0,0}, {sty,stx}});
    vi[sty][stx][0] = false;

    while(!q.empty()){
        int cd = q.front().xx.xx;
        int ck = q.front().xx.yy;
        int cy = q.front().yy.xx;
        int cx = q.front().yy.yy;
        q.pop();

        if(ck == (1<<K)-1) return cd;
        for(int i=0; i<4; i++){
            int nd = cd + 1;
            int nk = ck;
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny<0 || nx<0 || ny>=N || nx>=M || m[ny][nx]==-1) continue;
            if(m[ny][nx] > 0) nk |= (1<<(m[ny][nx]-1));
            if(vi[ny][nx][nk]) continue;
            q.push({{nd,nk}, {ny,nx}});
            vi[ny][nx][nk] = true;
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(1){
        cin>>M>>N;
        if(!N) break;
        memset(m,-1,sizeof(m));
        int sty, stx, K=0;
        string str;
        for(int i=0; i<N; i++){
            cin>>str;
            for(int j=0; j<M; j++){
                if(str[j] == 'o') sty = i, stx = j, m[i][j] = 0;
                else if(str[j] == '*') m[i][j] = ++K;
                else if(str[j] == 'x') m[i][j] = -1;
                else m[i][j] = 0;
            }
        }

        cout<<bfs(sty, stx, K)<<'\n';
    }
}