4991 로봇 청소기

문제 링크

• 문제 풀이

bfs를 이용하여 먼지간 간격을 저장한다. 먼지의 간격을 측정한후 최단거리를 구하는 알고리즘을 이용한다.

문제점 : 속도가 느림

이유 : bfs를 이용한 탐색과정에서 많은 조건문으로 인해 속도가 저하되었다.

• 개선된 풀이

맵의 양 테두리에 접근 불가능한 값을 넣어 조건문을 간소화 하여 속도를 개선함

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>

#define INF (int)2e9

using namespace std;

void bfs(pair<int, int>);
int go(int, int);

int W, H;
map<pair<int, int>, int> m;
char input[22][22];
int visited[22][22];
pair<int, int> dirty[12];
vector<pair<int, int>> x_place;
int E[12][12];
int D[12][1 << 11];
int N = 1;

int main(void)
{
    while (1) {
        memset(D, -1, sizeof(D));

        scanf("%d %d", &W, &H);
        if (W == 0 && H == 0)
            break;

        for (int i = 1; i <= H; i++) {
            getchar();
            for (int j = 1; j <= W; j++) {
                scanf("%c", &input[i][j]);

                if (input[i][j] == 'o') {
                    dirty[1] = make_pair(i, j);
                    m.insert(make_pair(make_pair(i, j), 1));
                }

                if (input[i][j] == '*') {
                    N++;
                    dirty[N] = make_pair(i, j);
                    m.insert(make_pair(make_pair(i, j), N));
                }

                if (input[i][j] == 'x')
                    x_place.push_back(make_pair(i, j));
            }
        }

        for (int i = 1; i <= N; i++)
            bfs(dirty[i]);

        int res = go(1, 1);

        if (res == INF)
            printf("%d\n", -1);
        else
            printf("%d\n", res);

        m.clear();
        x_place.clear();
        N = 1;
        memset(E, 0, sizeof(E));
        memset(visited, 0, sizeof(visited));
    }

    return 0;
}

void bfs(pair<int, int> v)
{
    queue<pair<int, int>> Q;

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

    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++)
            visited[i][j] = INF;

    for (auto x : x_place)
        visited[x.first][x.second] = 0;

    visited[v.first][v.second] = 0;
    Q.push(v);

    while (!Q.empty()) {
        int curx = Q.front().first;
        int cury = Q.front().second;
        Q.pop();

        if (input[curx][cury] == '*')
            E[m[v]][m[make_pair(curx, cury)]] = visited[curx][cury];

        for (int i = 0; i < 4; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];

            if (visited[curx][cury] + 1 < visited[nx][ny]) {
                visited[nx][ny] = visited[curx][cury] + 1;
                Q.push(make_pair(nx, ny));
            }
        }
    }

    return;
}

int go(int cur, int bitmask)
{
    if (bitmask == (1 << N) - 1)
        return 0;

    int& ret = D[cur][bitmask];

    if (ret != -1)
        return ret;

    ret = INF;

    for (int i = 2; i <= N; i++)
        if (E[cur][i] && !(bitmask & 1 << (i - 1)))
            ret = min(ret, go(i, bitmask | 1 << (i - 1)) + E[cur][i]);

    return ret;
}