BOJ12908 텔레포트3(C++)

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

태그 : 구현, 그래프, 다익스트라

사고 흐름

제목만 봤을 때는 단순 bfs류 냄새가 났으나..

읽고나서 든 생각은 브루트포스였다. 하지만 구현하다보니 뭔가 이상해졌다.

의심하면서 태그를 봤고, 그래프/최단경로 태그를 보고 다익스트라로 풀이를 변경했다.

그냥 출발지 0번, 도착지 1번, 나머지 점 6개를 정점으로 놓고,

순간이동 되는 점끼리만 min(순간이동, 점프로 이동)으로 거리를 체크해주었다.

queue도 사용할 필요 없이 그냥 무식하게 7번 정점을 갱신했다.

#include <iostream>
#include <algorithm>
using namespace std;

const long long INF = 1e18;

int xs, ys, xe, ye;
pair<int, int> v[8];
long long  graph[8][8];
long long dist[8];
int visited[8];
long long ans;

void solve() {
    for (int i = 0; i < 8; ++i) {
        for (int j = i; j < 8; ++j) {
            if (i != j) {
                long long dist = abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second);
                if (graph[i][j]) {
                    graph[i][j] = min(graph[i][j], dist);
                    graph[j][i] = min(graph[j][i], dist);
                }
                else {
                    graph[i][j] = dist;
                    graph[j][i] = dist;
                }
            }
        }
    }

    dist[0] = 0;
    visited[0] = 1;

    for (int i = 1; i < 8; ++i) {
        dist[i] = graph[0][i];
    }

    int cnt = 7;

    while (cnt--) {
        long long m = INF;
        int idx = 0;

        for (int i = 1; i < 8; ++i) {
            if (!visited[i] && dist[i] < m) {
                m = dist[i];
                idx = i;
            }
        }
        visited[idx] = 1;
        for (int i = 0; i < 8; ++i) {
            dist[i] = min(dist[i], dist[idx] + graph[idx][i]);
        }
    }
    ans = dist[1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> xs >> ys >> xe >> ye;
    v[0] = { xs, ys };
    v[1] = { xe, ye };
    graph[0][1] = graph[1][0] = abs(xs - xe) + abs(ys - ye);

    for (int i = 2; i < 8; ++i) {
        int a, b;
        cin >> a >> b;
        v[i] = { a, b };
        if (i % 2) {
            graph[i][i - 1] = 10;
            graph[i - 1][i] = 10;
        }
    }
    solve();
    cout << ans;
}

후기

생각나면 브루트포스로도 구현 해봐야겠다.

또 데이터 크기 관련 실수를 했다. INF를 1,000,000,007로 놨다가 벼락맞았다.