[BOJ] 16952 체스판 여행 2

문제 링크

www.acmicpc.net/problem/16952

풀이

체스판의 크기가 최대 10 by 10이고 말의 개수가 3개이므로 상태공간의 크기는 300으로 나타낼 수 있다.
한 상태에서 다른 상태로 가는 최단 거리를 다익스트라로 구하고 이를 그래프로 구축한 뒤 플로이드 워셜을 썼다.

당연히 최적의 풀이는 아니며, 매우 비효율적인 풀이지만 그래도 통과는 된다.

C++ 코드

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) int(size(x))
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.tie(nullptr)->sync_with_stdio(false)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
constexpr int MOD = 1e9 + 7;
constexpr int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
constexpr int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

pii operator+(const pii& a, const pii& b) {
    return pii(a.X + b.X, a.Y + b.Y);
}

int main() {
    fastio;
    int N;
    cin >> N;

    int bo[10][10];
    pii pos[101];
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> bo[i][j];
            pos[--bo[i][j]] = { i, j };
        }
    }

    vector<pii> unit[3] = {
        {
            { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 },
            { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 }
        },
        {
            { -1, -1 }, { -1, 1 }, { 1, -1 }, { 1, 1 }
        },
        {
            { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }
        }
    };

    pii adj[300][300]; fill(&adj[0][0], &adj[299][299], pii(0x3f3f3f3f, 0x3f3f3f3f));
    int T = N * N * 3;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int s = 0; s < 3; ++s) {
                int val = i * N * 3 + j * 3 + s;
                pii dist[300]; fill(dist, dist + 300, pii(0x3f3f3f3f, 0x3f3f3f3f));
                dist[val] = pii(0, 0);

                priority_queue<pair<pii, int>, vector<pair<pii, int>>, greater<>> PQ;
                PQ.emplace(pii(0, 0), val);

                while (!PQ.empty()) {
                    auto now = PQ.top(); PQ.pop();
                    if (dist[now.Y] < now.X) continue;

                    int x = now.Y / N / 3;
                    int y = now.Y % (N * 3) / 3;
                    int s = now.Y % 3;

                    if (s == 0) {
                        for (int ii = 0; ii < 8; ++ii) {
                            int nx = x + unit[0][ii].X;
                            int ny = y + unit[0][ii].Y;
                            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                            
                            int nxt = nx * N * 3 + ny * 3 + 0;
                            if (dist[nxt] <= now.X + pii(1, 0)) continue;

                            dist[nxt] = now.X + pii(1, 0);
                            PQ.emplace(dist[nxt], nxt);
                        }
                    }
                    else if (s == 1) {
                        for (int ii = 0; ii < 4; ++ii) {
                            for (int jj = 1; ; ++jj) {
                                int nx = x + unit[1][ii].X * jj;
                                int ny = y + unit[1][ii].Y * jj;
                                if (nx < 0 || nx >= N || ny < 0 || ny >= N) break;

                                int nxt = nx * N * 3 + ny * 3 + 1;
                                if (dist[nxt] <= now.X + pii(1, 0)) continue;

                                dist[nxt] = now.X + pii(1, 0);
                                PQ.emplace(dist[nxt], nxt);
                            }
                        }
                    }
                    else {
                        for (int ii = 0; ii < 4; ++ii) {
                            for (int jj = 1; ; ++jj) {
                                int nx = x + unit[2][ii].X * jj;
                                int ny = y + unit[2][ii].Y * jj;
                                if (nx < 0 || nx >= N || ny < 0 || ny >= N) break;

                                int nxt = nx * N * 3 + ny * 3 + 2;
                                if (dist[nxt] <= now.X + pii(1, 0)) continue;

                                dist[nxt] = now.X + pii(1, 0);
                                PQ.emplace(dist[nxt], nxt);
                            }
                        }
                    }

                    if (int nxt = x * N * 3 + y * 3 + (s + 1) % 3; dist[nxt] > now.X + pii(1, 1)) {
                        dist[nxt] = now.X + pii(1, 1);
                        PQ.emplace(dist[nxt], nxt);
                    }
                    if (int nxt = x * N * 3 + y * 3 + (s + 2) % 3; dist[nxt] > now.X + pii(1, 1)) {
                        dist[nxt] = now.X + pii(1, 1);
                        PQ.emplace(dist[nxt], nxt);
                    }
                }

                for (int k = 0; k < T; ++k) adj[val][k] = dist[k];
            }
        }
    }

    for (int k = 0; k < T; ++k)
        for (int i = 0; i < T; ++i) if (adj[i][k] != pii(0x3f3f3f3f, 0x3f3f3f3f))
            for (int j = 0; j < T; ++j)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

    pii ans[100][3]; fill(ans[0], ans[99] + 3, pii(0x3f3f3f3f, 0x3f3f3f3f));
    fill(ans[0], ans[0] + 3, pii(0, 0));
    for (int i = 0; i < N * N - 1; ++i) {
        for (int s = 0; s < 3; ++s) {
            int now = pos[i].X * N * 3 + pos[i].Y * 3 + s;
            for (int ss = 0; ss < 3; ++ss) {
                int nxt = pos[i + 1].X * N * 3 + pos[i + 1].Y * 3 + ss;
                ans[i + 1][ss] = min(ans[i + 1][ss], ans[i][s] + adj[now][nxt]);
                //cout << i + 1 << " -> " << i + 2 << ": " << adj[now][nxt].X << ' ' << adj[now][nxt].Y << "\t\t" << ans[i + 1][ss].X << ' ' << ans[i + 1][ss].Y << endl;
            }
            //cout << endl;
        }
        //cout << string(50, '=') << endl;
    }

    auto r = *min_element(ans[N * N - 1], ans[N * N - 1] + 3);
    cout << r.X << ' ' << r.Y;

    return 0;
}