4991번 로봇 청소기

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

지난 코드 : https://hsdevelopment.tistory.com/192

구현과 백트래킹 그리고 BFS을 모두 혼합한 문제를 공부할겸 다시 풀어보았다.

next_permutation()을 사용하지 않고, 구현하려고 하였으나, 이상하게 구현이 안 되었다. 

그래서, 사용하였더니 또 틀렸다.

이유는 알고보니,

1 1

o

0

위의 경우와

나는 단순히

while()을 사용했었는데, 처음인 경우(1, 2, 3, 4..)가 있어서

do ~ while()을 사용해야 한다.

시간도 거의 1/3이나 줄었다.

#include <bits/stdc++.h>
 
using namespace std;
 
int w = 0, h = 0, ans = 0, dist[11][11] = { 0, };
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
char Map[22][22];
 
vector<pair<int, int> > v;
 
vector<int> pt;
 
int bfs(pair<int, int> from, pair<int, int> to)
{
    int ret = 0;
 
    bool visit[22][22] = { false, };
 
    queue<pair<int, int> > q;
 
    q.push(from);
 
    visit[from.first][from.second] = true;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (r == to.first && c == to.second) return ret;
 
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= h || x < 0 || x >= w || visit[y][x] || Map[y][x] == 'x') continue;
 
                visit[y][x] = true;
                q.push({ y, x });
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
void init()
{
    for (int i = 0; i < 11; i++) for (int j = 0; j < 11; j++) dist[i][j] = 2e9;
 
    v.clear();
 
    pt.clear();
 
    ans = 2e9;
}
 
int main(void)
{
    while (1)
    {
        init();
 
        bool stop = false;
 
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) break;
 
        for (int i = 0; i < h; i++)
        {
            scanf("%s", Map[i]);
 
            for (int j = 0; j < w; j++)
                if (Map[i][j] == 'o') v.insert(v.begin(), { i, j });            
                else if (Map[i][j] == '*') v.push_back({ i, j });                
        }
 
        for (int i = 0; i < v.size() && !stop; i++)
            for (int j = 0; j < v.size() && !stop; j++)
            {
                if (i <= j) continue;
 
                dist[i][j] = dist[j][i] = bfs(v.at(i), v.at(j));
 
                if (dist[i][j] == -1) stop = true;
            }
 
        if (stop)
        {
            printf("-1\n");
            continue;
        }
    
        for (int i = 0; i < v.size() - 1; i++) pt.push_back(i + 1);
        
        do
        {
            int start = 0, sum = 0;
            for (auto i : pt)
            {
                sum += dist[start][i];
                start = i;
            }
            ans = min(ans, sum);
        } while (next_permutation(pt.begin(), pt.end()));
 
        if (ans == 2e9) ans = 0;
 
        printf("%d\n", ans);
    }
 
    return 0;
}