[C++] 포항항 (백준 23817번)

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

 

이 문제 풀 때 고수들이 옆에 있었어서 그들이 걍 다 해줌. 저는 풀이를 듣고 음 그렇구나. 천재다. 구현해볼게. 했음다.

 

첫번째 풀이.

 

vst 배열: 현재 위치 (i, j) + 어느어느식당 방문했는지 (길이가 20인 비트스트링)
길이가 20인 비트스트링 → 2^20 하면 너무 큼 → 근데 어차피 최대가 5개 켜지는 거임 → 2^20 중에 안 쓰는 게 너무 많음 (어떤 걸 안 쓰는지 모름) → map 이용

vector<vector<map<int, int>>> → 최단 거리를 두번째 int에 저장하는 셈
vector<vector<map<int, bool>>> (= vector<vector<set<int>>>) → 방문 했는지 안 했는지를 bool에 저장하는 셈

근데 이렇게 하면 터짐...

 

두번째 풀이.

모든 식당과 식당 (+시작점) 사이의 거리를 구한다 -> 21*21개
그 21*21개 중에서 어느어느 식당 5개를 골라서 어떤 순서로 방문할지 permutation으로 최단 경로 찾기

이 때는 백트래킹 사용

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, kn, si, sj;
vector<string> a;
vector<vector<int>> vst;
vector<int> ki;
vector<int> kj;
vector<vector<int>> b;
vector<bool> chk;
int ans = -1;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(int kt) {
    int i = ki[kt];
    int j = kj[kt];

    vst = vector<vector<int>>(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    q.emplace(i, j);
    vst[i][j] = 0;

    while (!q.empty()) {
        int curi = q.front().first;
        int curj = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nxti = curi + dx[k];
            int nxtj = curj + dy[k];
            if (nxti >= 0 && nxti < n && nxtj >= 0 && nxtj < m && a[nxti][nxtj] != 'X' && vst[nxti][nxtj] < 0) {
                q.emplace(nxti, nxtj);
                vst[nxti][nxtj] = vst[curi][curj] + 1;
            }
        }
    }

    for (int k = 0; k < kn; k++) {
        if (ki[k] == si && kj[k] == sj) continue;
        b[kt][k] = vst[ki[k]][kj[k]];
    }
}

void dfs(int cur, int cnt, int time) {
    if (cnt == 5) {
        if (ans == -1) ans = time;
        else ans = min(ans, time);
    } else if (cnt < 5) {
        for (int nxt = 0; nxt < kn - 1; nxt++) {
            if (!chk[nxt] && b[cur][nxt] != -1) {
                chk[nxt] = 1;
                dfs(nxt, cnt + 1, time + b[cur][nxt]);
                chk[nxt] = 0;
            }
        }
    }
}

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

    cin >> n >> m;
    a = vector<string>(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'S') {
                si = i;
                sj = j;
            } else if (a[i][j] == 'K') {
                ki.push_back(i);
                kj.push_back(j);
            }
        }
    }

    ki.push_back(si);
    kj.push_back(sj);
    kn = ki.size();

    b = vector<vector<int>>(kn, vector<int>(kn, -1));

    for (int k = 0; k < kn; k++) bfs(k);

    chk = vector<bool>(kn, 0);
    dfs(kn - 1, 0, 0);

    cout << ans << '\n';
}

(AC)