백준 g1 4991 로봇 청소기 c++

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

4991번: 로봇 청소기

 

문제 설명

• M, N 크기의 방에 *: 더러운 칸, x: 가구, o: 로봇 청소기의 시작 위치가 존재한다.
• 더러운 칸의 개수는 10개를 넘지 않으며, 방 크기는 최대 20*20이다.
• 로봇청소기 시작 위치에서 더러운 칸을 모두 깨끗한 칸으로 청소할 때, 이동횟수의 최솟값 구하기
  • 방문했던 곳 다시 방문 가능

 

풀이

 

1. 먼지의 개수가 10개 이하이므로, 무슨 먼지부터 청소할 건지 정하는 순열(10!)을 구한다.

2. 순열에 맞춰 시작 위치-> 0번째 먼지-> 1번째 먼지-> ... -> 마지막 먼지까지 가는 거리의 합을 구한다.

    - 이때 최소 거리는 BFS로 구한다. 그러나 먼지를 구할 때마다 거리를 구하면 시간 낭비이다. 왜냐하면 특정 위치 -> 특정 위치로 가는 거리는 여러 번 쓰일 수 있기 때문이다. ex. 어떤 경우에서는 시작 위치 -> 1번째 먼지일 수도 있고, 어떤 경우에는 시작 위치 -> 3번째 먼지일 수도 있다. 이때 시작 위치에서 모든 먼지로 가는 거리를 BFS로 한 번에 구해놓으면 그 다음 번에는 따로 구할 필요 없이 이전에 구해놓았던 거리를 불러오면 된다.

 

 

1. 순열은 next_permutation으로 구했다. 

permutation[i] : i번째로 오는 먼지의 번호

vector dirty: i번 먼지의 위치

<input 함수>
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (board[i][j] == '*') {
            dirty.push_back({i, j});
            permutation.push_back(permutation.size());
        } 
        ...
    }
}

<main 함수>

do {
	...
} while(next_permutation(permutation.begin(), permutation.end());

 

2. getDistance() 함수

bool getDistance() { // 시작점 -> 먼지 순열, 갈 수 있으면 true 없으면 false를 반환
    ans = 0;
    for (int v = 0; v < permutation.size(); v++) { // v-1, v와의 거리 / v==0일 때는 시작점과
        int sx, sy, ex, ey;
        if (v == 0) {
            // 1. 시작점 -> 먼지 순열
            sx = start.first;
            sy = start.second;
        } else {
            // v가 1 이상일 때, v-1과 v와의 거리
            sx = dirty[permutation[v - 1]].first;
            sy = dirty[permutation[v - 1]].second;
        }

        ex = dirty[permutation[v]].first;
        ey = dirty[permutation[v]].second;
		
        
        //거리 이미 구해져 있으면 그거 쓰고, 아니면 bfs 새로
        int d = dist[sx][sy][ex][ey] != 0 ? dist[sx][sy][ex][ey] : bfs(sx, sy, ex, ey);

        if (d == 0)
            return false;
        else
            ans += d;
    }
    return true;
}

 

 

 

전체 코드

/*boj g1 4991 로봇 청소기*/
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

#define MAXN 22
#define INF 9999
using namespace std;

int N, M;
string board[MAXN];
int vis[MAXN][MAXN];              // bfs 돌릴 때마다 clear
int dist[MAXN][MAXN][MAXN][MAXN]; // i, j -> x, y로 가는 거리 저장
vector<pair<int, int>> dirty;
vector<int> permutation;

pair<int, int> start;
int mn = INF;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void initialize() {
    dirty.clear();
    permutation.clear();
    mn = INF;

    for (int i = 0; i < MAXN; i++)
        board[i] = "";

    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            for (int a = 0; a < MAXN; a++)
                for (int b = 0; b < MAXN; b++)
                    dist[i][j][a][b] = 0;
}

void input() {
    cin >> M >> N;
    if (N == 0 && M == 0)
        exit(0);

    for (int i = 0; i < N; i++) {
        cin >> board[i];
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == '*') {
                dirty.push_back({i, j});
                permutation.push_back(permutation.size());
            } else if (board[i][j] == 'o') {
                start.first = i;
                start.second = j;
            }
        }
    }
}

int bfs(int sx, int sy, int ex, int ey) {
    queue<pair<int, int>> Q;

    Q.push({sx, sy});
    dist[sx][sy][sx][sy] = 1;

    while (!Q.empty()) {
        int x, y;
        tie(x, y) = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (board[nx][ny] == 'x') continue;
            if (dist[sx][sy][nx][ny] > 0) continue; // 이미 방문함

            dist[sx][sy][nx][ny] = dist[sx][sy][x][y] + 1;
            Q.push({nx, ny});
        }
    }

    return dist[sx][sy][ex][ey];
}

int ans = 0;
bool getDistance() { // 시작점 -> 먼지 순열
    ans = 0;
    for (int v = 0; v < permutation.size(); v++) { // v-1, v와의 거리 / v==0일 때는 시작점과
        int sx, sy, ex, ey;
        if (v == 0) {
            // 1. 시작점 -> 먼지 순열
            sx = start.first;
            sy = start.second;
        } else {
            // v가 1 이상일 때, v-1과 v와의 거리
            sx = dirty[permutation[v - 1]].first;
            sy = dirty[permutation[v - 1]].second;
        }

        ex = dirty[permutation[v]].first;
        ey = dirty[permutation[v]].second;

        int d = dist[sx][sy][ex][ey] != 0 ? dist[sx][sy][ex][ey] : bfs(sx, sy, ex, ey);

        if (d == 0)
            return false;
        else
            ans += d;
    }
    return true;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    while (1) {
        initialize();
        input();

        do {
            bool res = getDistance(); // false면 도달할 수 없음

            if (res) {
                mn = min(mn, ans);
            }
        } while (next_permutation(permutation.begin(), permutation.end()));

        if (mn == INF)
            cout << -1 << "\n";
        else
            cout << mn - dirty.size() << "\n";
    }
}