[BOJ] 4991 : 로봇 청소기

4991 : 로봇 청소기

풀이

BFS

처음생각보다 훨씬 어려웠던 문제.

단순히 가까운점 부터 탐색을 시키니 최소를 보장 할 수 없는 문제가 생겼다.

( * o * * ) 대충 이럴경우 조금 더 거리가 먼 왼쪽부터 먹고 오른쪽으로 향하는게 더 빠르다.

배열에 메모이제이션해놓고 거리를 먼저 다 구해준다음에 next_permutation으로 조합을 짜서 풀었다.

그런데 이때 그냥 대충 o(시작점)도 *로 바꾸고 풀었더니 경로가 꼬이는 문제가 있었다.

그래서 vector<pair<int, int» dirt(1) 를 하고, 시작점이면 dirt[0] = make_pair(i, j)

아닐경우 dirt.push_back({i,j}) 를 하는 방법을 사용했다. (백준님 코드 참고함)

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
int w, h;
string map[20];
//dist[a][b] : a->b distance
int dist[11][11];

void bfs(int idx, vector<pair<int, int>> &dirt) {
    int chk[20][20] = { 0 };
    queue<pair<pair<int, int>, int>> q;
    q.push({ {dirt[idx].first,dirt[idx].second} ,0 });
    chk[dirt[idx].first][dirt[idx].second] = 1;
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int d = q.front().second;
        q.pop();
        if (map[x][y]=='*') {
            for (int i = 0; i < dirt.size(); i++) {
                if (dirt[i].first == x && dirt[i].second == y) {
                    dist[idx][i] = d;
                    break;
                }
            }
        }
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 0 && nx < h&&ny >= 0 && ny < w&&map[nx][ny] != 'x' && chk[nx][ny]==0) {
                chk[nx][ny] = 1;
                q.push({ {nx,ny},d+1 });
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> w >> h;
    while (w || h) {
        memset(dist, -1, sizeof(dist));
        for (int i = 0; i < h; i++) {
            cin >> map[i];
        }
        //시작점은 0번째를 보장해야한다.
        vector<pair<int, int>> dirt(1);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] == 'o') {
                    map[i][j] = '*';
                    dirt[0] = make_pair(i, j);
                }
                else if (map[i][j] == '*') {
                    dirt.push_back({i,j});
                }
            }
        }
        int flag = 0;
        for (int i = 0; i < dirt.size(); i++) {
            bfs(i, dirt);
            for (int j = 0; j < dirt.size(); j++) {
                if (dist[i][j] == -1) {
                    flag = 1;
                    break;
                }
            }
            if (flag)
                break;
        }
        if (flag) {
            cout << -1 << '\n';
        }
        else {
            int ans = 987654321;
            //점 방문 순서 조합
            vector<int> num;
            //시작점 빼고
            for (int i = 1; i < dirt.size(); i++) {
                num.push_back(i);
            }
            do {
                int tmp = dist[0][num[0]];
                for (int i = 0; i < dirt.size() - 2;i++) {
                    tmp += dist[num[i]][num[i + 1]];
                }
                if (ans > tmp) {
                    ans = tmp;
                }
            } while (next_permutation(num.begin(),num.end()));
            cout << ans << '\n';
        }
        
        cin >> w >> h;
    }
    return 0;
}


Written on May 26, 2019