[백준] 4991 로봇 청소기

정말정말저마렂아멀장 마음아픈 문제다

다 맞춰놓고 오버플로우가 생기게 코드를 짜서 쓸데없이 시간 낭비를 했다

하하하하하 코드... inf값을 10억으로 막놨더니 100억까지 초과된다...

이걸 못찾고 계속 로직을 바꾸려 해서 나의 아까운 시간을.....

inf값 생각없이 막 두면 안되겠다..

문제를 푸는 방법은

1. 더러운 칸들을 번호를 매겨 벡터에 넣는다

2. 각각의 더러운 칸들에서 bfs를 돌려 저장해준다

3. next_permutation을 통해 언제가 가장 가까운지 구하면 된다!

만약 갈수 없다면 -1을 출력해준다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n, m;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int dist[22][22][22];
bool check[22][22][22];
char map[22][22];
vector<pair<pair<int, int>, int>> trash;
int sx, sy;
void bfs(int x, int y, int pos) {
    queue<pair<int, int>> q;
    q.push({ x,y });
    dist[x][y][pos] = 0;
    check[x][y][pos] = true;
    while (!q.empty()) {
        int px = q.front().first;
        int py = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = px + dx[i];
            int ny = py + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (!check[nx][ny][pos] && map[nx][ny] != 'x') {
                    check[nx][ny][pos] = true;
                    dist[nx][ny][pos] = dist[px][py][pos] + 1;
                    q.push({ nx,ny });
                }
            }
        }
    }
}
int main() {
    while (scanf(" %d %d", &m, &n) != -1) {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < 22; i++) {
            for (int j = 0; j < 22; j++) {
                for (int k = 0; k < 22; k++) {
                    dist[i][j][k] = 1e5;
                }
            }
        }
        memset(check, 0, sizeof(check));
        memset(map, 0, sizeof(map));
        trash.clear();
        sx = sy = 0;
        int tcnt = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf(" %1c", &map[i][j]);
                if (map[i][j] == '*') trash.push_back({ { i,j }, tcnt++ });
                if (map[i][j] == 'o')sx = i, sy = j;
            }
        }
        int ans = 1e5;
        int cnt = trash.size();
        if (cnt == 0) {
            puts("0"); continue;
        }
        bfs(sx, sy, 0);
        sort(trash.begin(), trash.end());
        for (int i = 0; i < cnt; i++) bfs(trash[i].first.first, trash[i].first.second, trash[i].second);
        do {
            int temp = dist[trash[0].first.first][trash[0].first.second][0];
            for (int i = 0; i < cnt - 1; i++) temp += dist[trash[i + 1].first.first][trash[i + 1].first.second][trash[i].second];
            ans = min(ans, temp);
        } while (next_permutation(trash.begin(), trash.end()));
        printf("%d\n", ans == 1e5 ? -1 : ans);
    }
}

추가로 모든 정점에서 미리 bfs를 돌리는 방법도 있다

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n, m, sx, sy, inf = 1e9;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int dist[22][22][22][22];
bool check[22][22][22][22];
char map[22][22];
vector<pair<int, int>> vt;
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({ x,y });
    check[x][y][x][y] = true;
    dist[x][y][x][y] = 0;
    while (!q.empty()) {
        int ax = q.front().first;
        int ay = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = ax + dx[i];
            int ny = ay + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (!check[nx][ny][x][y] && map[nx][ny] != 'x') {
                    check[nx][ny][x][y] = true;
                    dist[nx][ny][x][y] = dist[ax][ay][x][y] + 1;
                    q.push({ nx,ny });
                }
            }
        }
    }
}
int main() {
    while (scanf(" %d %d", &m, &n) != -1) {
        if (n == 0 && m == 0) return 0;
        memset(check, 0, sizeof(check));
        memset(map, 0, sizeof(map));
        vt.clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    for (int l = 0; l < m; l++) {
                        dist[i][j][k][l] = inf;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf(" %1c", &map[i][j]);
                if (map[i][j] == 'o') sx = i, sy = j;
                else if (map[i][j] == '*') vt.push_back({ i,j });
            }
        }
        if (vt.size() == 0) {
            puts("0"); continue;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                bfs(i, j);
            }
        }
        int cnt = vt.size();
        int ans = 1e9;
        sort(vt.begin(), vt.end());
        bool ok = true;
        do {
            int temp = dist[vt[0].first][vt[0].second][sx][sy];
            for (int i = 1; i < cnt; i++) temp += dist[vt[i].first][vt[i].second][vt[i - 1].first][vt[i - 1].second];
            if (temp >= 1e9) {
                ok = false; break;
            }
            ans = min(ans, temp);
        } while (next_permutation(vt.begin(), vt.end()));
        if (!ok) puts("-1");
        else printf("%d\n", ans);
    }
}