[백준] 4991 로봇 청소기 (C++)

문제

4991번: 로봇 청소기 (acmicpc.net)

4991번: 로봇 청소기

 

 

 

풀이

위의 문제를 해결하기 위한 여러가지 방법이 있습니다.
우선 각각의 더러운 곳과 로봇의 위치를 노드로하는 그래프를 구하는 것이 좋습니다. bfs 탐색으로 각각의 거리를 간선의 가중치로하는 완전 그래프를 얻을 수 있습니다. 문제에서의 방 크기가 최대 20 x 20이고 최대 노드의 개수는 11개로, 큰 비용없이 그래프를 얻을 수 있습니다. 

 

이제 이 그래프를 활용하여 문제를 해결해봅시다.

 

 

방법1 (완전 탐색)

문제에서 주어진 수가 크지 않으므로 완전탐색을 할 수 있습니다.

모든 노드들을 순회해야 하고, 각 노드들의 순회 순서에 따라 이동 거리가 달라지므로 모든 경우의 수를 확인합니다.

 

이는 노드를 줄세우는 순열 문제이고, dfs 완전탐색으로 구현할 수 있습니다.
그러므로 시간복잡도는 $O(n!)$로, 10! = 3,628,800 으로 해결 가능합니다.

(11개의 노드지만 시작점은 고정으로 10개의 노드 순열을 구한다.)

 

 

방법2 (TSP: 외판원 순회)

방법1에서 언급했듯이 모든 노드들을 순회하고, 각 노드들의 모든 순회 순서를 고려해야 하는 문제로 귀착되었다고 볼 수 있습니다. 그렇다면 이 문제는 외판원 순회 문제를 푸는것과 정말 유사합니다. (마지막 노드에서 시작 노드로 돌아오지 않는 다는 점이 다르긴 합니다.)

 

수많은 중복된 경우의 수를 배제하고 답을 찾기 때문에 방법1보다 훨씬 빠른 속도로 최소 이동거리를 얻을 수 있습니다.
시간복잡도는 $O(2^{n} n^{2})$입니다.

 

 

방법3 (bfs + 비트 마스킹)

최소 이동거리는 bfs 탐색으로 구할 수 있습니다. 이 문제에서도 마찬가지로 bfs 탐색으로 구할 수 있습니다.

이때 어떤 노드를 방문한 상태인지에 따라 중복을 제거해야 합니다.

같은 위치라도 1번 노드를 방문한 상태와, 1번, 2번 노드를 방문한 상태는 다르게 적용됩니다.

 

이렇게 어떤 노드를 방문했는가에 대한 정보를 저장하기 위해 비트마스킹을 활용합니다.

같은 위치라도 비트마스킹으로 표현된 수가 다르다면 이동할 수 있습니다.

구현을 한다면 visited[x][y][k]로 표현하여 x, y 위치에서 k로 표현된 방문 노드를 확인하여 중복을 제거합니다.

 

각 노드가 실제 방에서 어떤 위치인지, 방에서의 더러운 곳의 위치가 어떤 노드 번호를 갖는지 저장해두면 편리하게 비트마스킹을 활용할 수 있습니다.

 

 

방법3을 적용하기 위해서는 더러운곳을 노드하는 완전 그래프로의 변환이 필요하지 않습니다.

하지만 완전 그래프로 변환한 상태에서도 탐색할 수 있습니다.

그래프의 간선 가중치 값이 이동거리이기 때문에 여태 방문한 간선 가중치들의 합이 현재 총 이동거리가 되고 그 이동거리를 기준으로 하는 우선 순위 큐를 이용한다면 2차원 보드에서 bfs 탐색하듯이 가까운 곳을 항상 먼저 탐색하게 됩니다.

 

visited[x][y][k] 같은 커다란 배열을 사용하지 않고, 큐 안에 방문한 노드들에 대한 정보를 넣어 그 노드를 방문 했는지 검사합니다. 이때 방문 노드에 대한 정보도 비트마스킹으로 표현합니다.

만약 모든 노드를 탐색하여 visited == (1 << nodeCnt) - 1 이라면 탐색을 종료하고 그때의 이동거리를 출력합니다.

 

 

 

코드

방법2

#include <iostream>
#include <vector>

using namespace std;

int w, h;
vector<vector<char>> board;
vector<vector<int>> graph;
vector<pair<int, int>> nodePos;
int nodeCnt = 1;
vector<vector<int>> memo;

bool OOB(int x, int y)
{
    return x < 0 || x >= h || y < 0 || y >= w;
}

int min(int a, int b) { return a < b ? a : b; }

bool input()
{
    cin >> w >> h;
    board.assign(h, vector<char>(w));
    nodePos.resize(1);
    
    if (w == 0 && h == 0)
        return false;

    for (int i=0; i<h; ++i)
    {
        for (int j=0; j<w; ++j)
        {
            cin >> board[i][j];
            if (board[i][j] == 'o')
            {
                nodePos[0] = {i, j};
            }

            else if (board[i][j] == '*')
            {
                nodePos.push_back({i, j});
            }
        }
    }
    nodeCnt = nodePos.size();
    graph.assign(nodeCnt, vector<int>(nodeCnt, -1));
    memo.assign(nodeCnt, vector<int>(1 << nodeCnt, INT32_MAX));

    return true;
}

void bfs(int start)
{
    pair<int, int> startNode = nodePos[start];
    struct Params
    {
        int x;
        int y;
        int dist;
    };
    vector<pair<int, int>> dir { {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
    
    queue<Params> q;
    vector<vector<bool>> visited(h, vector<bool>(w, false));
    q.push({startNode.first, startNode.second, 0});
    visited[startNode.first][startNode.second] = true;
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int dist = q.front().dist;
        q.pop();


        if(board[x][y] == '*' || board[x][y] == 'o') 
        {
            for (int i=0; i<nodeCnt; ++i)
            {
                if (nodePos[i].first == x && nodePos[i].second == y)
                {
                    graph[start][i] = dist;
                }
            }
        }

        for (auto d : dir)
        {
            int nx = x + d.first;
            int ny = y + d.second;

            if (OOB(nx, ny))
                continue;

            if (board[nx][ny] == 'x')
                continue;
            
            if (visited[nx][ny])
                continue;

            visited[nx][ny] = true;
            q.push({nx, ny, dist+1});

        }
    }
}

bool makeGraph()
{
    for (int i=0; i<nodePos.size(); ++i)
    {
        bfs(i);
    }

    for (auto node : graph)
    {
        for (auto edge : node)
        {
            if (edge == -1)
                return false;
        }
    }

    return true;
}

int TSP(int cur, int visited)
{
    if (visited == (1 << nodeCnt) - 1)
    {
        return 0;
    }

    if (memo[cur][visited] != INT32_MAX)
    {
        return memo[cur][visited];
    }

    for (int i=0; i<nodeCnt; ++i)
    {
        if (visited & 1 << i)
            continue;

        int dist = TSP(i, visited | (1 << i));
        memo[cur][visited] = min(memo[cur][visited], dist + graph[cur][i]);
    }

    return memo[cur][visited];
}

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

    while (input())
    {
        int ans = -1;
        if (makeGraph())
        {
            ans = TSP(0, 1);
        }

        cout << ans << "\n";
        graph.clear();
    }
    return 0;
}

 

 

 

방법3 (우선순위 큐)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int w, h;
vector<vector<char>> board;
vector<vector<int>> graph;
vector<pair<int, int>> nodePos;
int nodeCnt = 1;

bool OOB(int x, int y)
{
    return x < 0 || x >= h || y < 0 || y >= w;
}

bool input()
{
    cin >> w >> h;
    board.assign(h, vector<char>(w));
    nodePos.resize(1);
    
    if (w == 0 && h == 0)
        return false;

    for (int i=0; i<h; ++i)
    {
        for (int j=0; j<w; ++j)
        {
            cin >> board[i][j];
            if (board[i][j] == 'o')
            {
                nodePos[0] = {i, j};
            }

            else if (board[i][j] == '*')
            {
                nodePos.push_back({i, j});
            }
        }
    }
    nodeCnt = nodePos.size();
    graph.assign(nodeCnt, vector<int>(nodeCnt, -1));

    return true;
}

void bfs(int start)
{
    pair<int, int> startNode = nodePos[start];
    struct Params
    {
        int x;
        int y;
        int dist;
    };
    vector<pair<int, int>> dir { {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
    
    queue<Params> q;
    vector<vector<bool>> visited(h, vector<bool>(w, false));
    q.push({startNode.first, startNode.second, 0});
    visited[startNode.first][startNode.second] = true;
    
    while(!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int dist = q.front().dist;
        q.pop();


        if(board[x][y] == '*' || board[x][y] == 'o') 
        {
            for (int i=0; i<nodeCnt; ++i)
            {
                if (nodePos[i].first == x && nodePos[i].second == y)
                {
                    graph[start][i] = dist;
                }
            }
        }

        for (auto d : dir)
        {
            int nx = x + d.first;
            int ny = y + d.second;

            if (OOB(nx, ny))
                continue;

            if (board[nx][ny] == 'x')
                continue;
            
            if (visited[nx][ny])
                continue;

            visited[nx][ny] = true;
            q.push({nx, ny, dist+1});

        }
    }
}

bool makeGraph()
{
    for (int i=0; i<nodePos.size(); ++i)
    {
        bfs(i);
    }

    for (auto node : graph)
    {
        for (auto edge : node)
        {
            if (edge == -1)
                return false;
        }
    }

    return true;
}

int graphBFS()
{
    struct Params
    {
        int idx;
        int dist;
        int visited;
    };

    struct cmp
    {
        bool operator()(Params a, Params b)
        {
            return a.dist > b.dist;
        }
    };
    priority_queue<Params, vector<Params>, cmp> pq;

    pq.push({0, 0, 1});
    int answer = -1;
    
    while(!pq.empty())
    {
        // cout << "bfs" << endl;
        int cur = pq.top().idx;
        int dist = pq.top().dist;
        int state = pq.top().visited;
        pq.pop();

        if (state ==((1 << nodeCnt) - 1))
        {
            answer = dist;
            return answer;
        }

        for (int i=1; i<nodeCnt; ++i)
        {
            if (graph[cur][i] <= 0)
                continue;

            if (state & 1 << i)
                continue;

            int nextDist = dist + graph[cur][i];
            int nextState = state | 1 << i;
            pq.push({i, nextDist, nextState});
        }
        
    }

    return answer;
}

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

    while (input())
    {
        int ans = -1;
        if (makeGraph())
        {
            // ans = TSP(0, 1);
            ans = graphBFS();
        }

        cout << ans << "\n";
        graph.clear();
    }
    return 0;
}