[BOJ 21817] 포항항

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

23817번: 포항항

Tag : bfs 

 

문제요약

2차원 격자에 시작점, 식당의 위치가 표기되어있다. 식당 중 5개를 골라 방문하는 최단거리를 구하라.

 

풀이

이 문제 너무한다. 나는 맵에 식당이 5개만 있는 줄 알았지... 

K = 식당의 개수 일 때 벡터에 K - 5개의 0과 5개의 1을 넣어서 next permutation을 돌리면 

방문할 식당 5개가 골라진다. 중복된 원소의 개수 때문에 이는 실제로 \(O(k C 5)\)에 돌아간다.

 

이제 방문할 식당을 골랐으니 순서도 골라야한다.

이건 고른 것 중에서 \(O(n!)\)의 순열을 모두 돌아보면 된다. 이렇게 넥퍼뮤를 두번 사용하면 

k P 5개를 고를 수 있다. 

 

그렇지만... 무슨 이유에서인지 이 구현에서 맞왜틀을 당하고 하드 코딩을 했다. 

이정도면 틀렸어도 한번만 봐주지....

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

#define int long long

int n, m, cnt = 0, ans = 1e9;
char v[1010][1010];
int dist[20][20];
vector<pair<int, int>> pos;
const int di[4] = {0, -1, 0, 1}, dj[4] = {-1, 0, 1, 0};

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> m;
    pair<int, int> S;
    vector<pair<int, int>> K;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) {
        cin >> v[i][j];
        if(v[i][j] == 'K') K.push_back({i, j});
        if(v[i][j] == 'S') S = make_pair(i, j);
    }
    pos.push_back(S);
    for(auto &i : K) pos.push_back(i);
    for(int i=0; i<20; i++) for(int j=0; j<20; j++) dist[i][j] = 1e9;
    auto bfs = [&](int idx)->void{
        queue<pair<int, int>> q;
        q.push(pos[idx]);
        vector<vector<int>> d(n + 1, vector<int>(m + 1, -1));
        d[pos[idx].first][pos[idx].second] = 0;
        while(q.size()) {
            auto [x, y] = q.front(); q.pop();
            for(int i=0; i<4; i++) {
                int ni = x + di[i], nj = y + dj[i];
                if(1 > ni or ni > n or 1 > nj or nj > m) continue;
                if(v[ni][nj] == 'X') continue;
                if(d[ni][nj] == -1) {
                    d[ni][nj] = d[x][y] + 1;
                    q.push({ni, nj});
                }
            }
        }
        for(int i=0; i<pos.size(); i++) {
            if(d[pos[i].first][pos[i].second] != -1) {
                dist[idx][i] = dist[i][idx] = d[pos[i].first][pos[i].second];
            }
        }
    };
    for(int i=0; i<pos.size(); i++) bfs(i);
    vector<int> path(6);
    for(path[1]=1; path[1]<pos.size(); path[1]++){
        for(path[2]=1; path[2]<pos.size(); path[2]++){
            for(path[3]=1; path[3]<pos.size(); path[3]++){
                for(path[4]=1; path[4]<pos.size(); path[4]++){
                    for(path[5]=1; path[5]<pos.size(); path[5]++){
                        vector<int> t = path;
                        sort(t.begin(), t.end()); t.erase(unique(t.begin(), t.end()), t.end());
                        if(t.size() != path.size()) continue;
                        int p = 0;
                        for(int i=1; i<6; i++) {
                            if(dist[path[i-1]][path[i]] >= 1e9) {
                                p = 1e9;
                                break;
                            }
                            p += dist[path[i-1]][path[i]];
                        }
                        ans = min(ans, p);
                    }
                }
            }
        }
    }
    if(ans >= 1e9) cout << -1 << endl;
    else cout << ans << endl;
}