백준 4991 - 로봇 청소기

문제 설명

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 로봇 청소기가 먼지를 모두 제거하는데 최소 거리를 구하면 된다.

 

가장 간단한 방법으로는 DFS를 통해 한칸씩 전진하며 먼지를 없애는 방법이 있다.

하지만, 해당 문제는 지나온 길을 다시 갈 수 있다.

따라서, 무한히 반복될 수 있다.

 

그렇다면 다른 접근법이 필요하다.

모든 먼지를 제거해야 하기 때문에 먼지를 제거하는 순서가 매우 중요하다.

순서에 따라 이동하는 거리가 달라지기 때문이다.

그러면 순열을 통해 먼지 방문 순서를 정한다고 생각해 보자.

만약, 먼지와 먼지 사이의 거리를 알고 있다하면 먼지를 방문하는 순서에 맞게 해당 거리를 구하면 된다.

단, 매번 BFS를 통해 거리를 구하면 시간이 많이 들 것이다.

따라서, 메모이제이션을 통해 모든 먼지 사이의 거리를 기록하여 필요할 때 참조해서 쓰면 된다.

 

BFS는 간단하다.

하나의 먼지를 시작점으로 정한 뒤, 모든 칸의 거리를 구하면 된다.

어차피 먼지의 위치는 고정되어 있고 모두 알고 있기 때문에 상수시간에 접근하여 사용할 수 있다.

그러면 3차원 배열이 필요하다.

//[기준][y][x]
int dist[11][21][21];

void BFS(vector<vector<char>> Room, vector<pair<int, int>>& dirty, int idx)
{
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < M; y++)
        {
            dist[idx][x][y] = INT_MAX;
        }
    }

    queue<pair<int, int>> q;
    dist[idx][dirty[idx].first][dirty[idx].second] = 0;
    q.push(dirty[idx]);

    while (!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int newY = y + dy[i];
            int newX = x + dx[i];

            if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue;
            if (Room[newY][newX] == 'x') continue;
            if (dist[idx][newY][newX] != INT_MAX) continue;

            dist[idx][newY][newX] = dist[idx][y][x] + 1;
            q.push({ newY, newX });
        }
    }
}

 

여기서 한 가지 처리할 것이 있다.

모든 경로의 시작은 로봇 청소기의 위치에서 시작한다는 것이다. 

즉, 로봇 청소기와 먼지사이의 거리도 알고 있어야 하기 때문에 로봇 청소기를 기준으로 BFS를 한 번 더 진행한다.

vector<vector<char>> Room(N, vector<char>(M));
pair<int, int> robot;
vector<pair<int, int>> dirty;

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        cin >> Room[i][j];
        if (Room[i][j] == 'o') robot = { i,j };
        if (Room[i][j] == '*') dirty.push_back({ i,j });
    }
}

dirty.push_back(robot);

for (int i = 0; i < dirty.size(); i++)
{
    BFS(Room, dirty, i);
}

관리하기 쉽게 먼지 배열의 끝에 로봇 청소기를 추가하였다.

따로 관리해도 무방하다.

 

이제, 순열을 생성하여 최소 거리를 구하면 된다.

하지만, 아까 말했듯이 시작은 로봇 청소기에서 시작되어야 한다.

따라서, 로봇 청소기를 제외하고 순열을 생성한 뒤, 로봇 청소기에서 출발한다고 생각하면 쉽다.

int currentIdx = dirty.size() - 1;
vector<int> order;
for (int i = 0; i < currentIdx; i++)
{
    order.push_back(i);
}

do
{
    int current = 0;
    currentIdx = dirty.size() - 1;

    for (int i = 0; i < order.size(); i++)
    {
        int nextIdx = order[i];
        int nextY = dirty[nextIdx].first;
        int nextX = dirty[nextIdx].second;
        if (dist[currentIdx][nextY][nextX] == INT_MAX)
        {
            current = INT_MAX;
            break;
        }

        current += dist[currentIdx][nextY][nextX];

        if (current >= ans) break;
        currentIdx = nextIdx;
    }

    ans = min(ans, current);
} while (next_permutation(order.begin(), order.end()));

for문의 중간에 방문 가능 여부를 판단하는 코드가 있다.

INT_MAX라는 뜻은 방문이 불가능하다는 뜻과 같기 때문에 더 이상 진행하지 않도록 했다.

하지만, 배열의 범위가 $20 * 20$이기 때문에 거리의 최댓값은 4000이다.

INT_MAX를 사용하지 않고 상수를 통해 4000을 사용해도 된다.

그렇다면 코드를 조금 더 깔끔하게 만들 수 있다.

현재 코드는 INT_MAX를 사용하여 int의 표현범위를 넘어가 이상한 값이 설정되어 위와 같이 처리한 것이다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, M;

vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };

int dist[11][21][21];

void BFS(vector<vector<char>> Room, vector<pair<int, int>>& dirty, int idx)
{
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < M; y++)
        {
            dist[idx][x][y] = INT_MAX;
        }
    }

    queue<pair<int, int>> q;
    dist[idx][dirty[idx].first][dirty[idx].second] = 0;
    q.push(dirty[idx]);

    while (!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int newY = y + dy[i];
            int newX = x + dx[i];

            if (newY < 0 || newY >= N || newX < 0 || newX >= M) continue;
            if (Room[newY][newX] == 'x') continue;
            if (dist[idx][newY][newX] != INT_MAX) continue;

            dist[idx][newY][newX] = dist[idx][y][x] + 1;
            q.push({ newY, newX });
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    while (true)
    {
        cin >> M >> N;
        if (N == 0 && M == 0) break;
        
        int ans = INT_MAX;

        vector<vector<char>> Room(N, vector<char>(M));
        pair<int, int> robot;
        vector<pair<int, int>> dirty;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                cin >> Room[i][j];
                if (Room[i][j] == 'o') robot = { i,j };
                if (Room[i][j] == '*') dirty.push_back({ i,j });
            }
        }

        dirty.push_back(robot);

        for (int i = 0; i < dirty.size(); i++)
        {
            BFS(Room, dirty, i);
        }

        int currentIdx = dirty.size() - 1;
        vector<int> order;
        for (int i = 0; i < currentIdx; i++)
        {
            order.push_back(i);
        }

        do
        {
            int current = 0;
            currentIdx = dirty.size() - 1;

            for (int i = 0; i < order.size(); i++)
            {
                int nextIdx = order[i];
                int nextY = dirty[nextIdx].first;
                int nextX = dirty[nextIdx].second;
                if (dist[currentIdx][nextY][nextX] == INT_MAX)
                {
                    current = INT_MAX;
                    break;
                }

                current += dist[currentIdx][nextY][nextX];

                if (current >= ans) break;
                currentIdx = nextIdx;
            }

            ans = min(ans, current);
        } while (next_permutation(order.begin(), order.end()));

        if (ans == INT_MAX) ans = -1;
        cout << ans << "\n";
    }


    return 0;
}

---