[BOJ] 14169 - Lasers and Mirrors

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

BOJ - Lasers and Mirrors

문제 유형: 다익스트라, 0-1 BFS, 최단 경로, 그래프, 좌표 압축

문제 난이도: Platinum V

시간 제한: 2초

메모리 제한: 512MB

 

문제

For some reason, Farmer John's cows always seem to be running laser light shows.

For their latest show, the cows have procured a large powerful laser -- so large, in fact, that they cannot seem to move it easily from the location where it was delivered. They would like to somehow send the light from the laser to the barn on the other side of FJ's property. Both the laser and the barn can be considered to be located at points in the 2D plane on a map of FJ's farm. The cows plan to point the laser so that it sends a beam of light out either horizontally or vertically (i.e., aligned with the x or y axes). They will then bounce this beam off a number of mirrors to direct it to the barn.

On the farm there are N fence posts (1≤N≤100,000) located at distinct 2D points (also distinct from the laser and the barn) at which the cows can mount mirrors. The cows can choose not to mount a mirror on a fence post, in which case the laser would simply pass straight over the top of the post without changing direction. If the cows do mount a mirror on a fence post, they align it diagonally like / or \ so that it will re-direct a horizontal beam of light in a vertical direction or vice versa.

Please compute the minimum possible number of mirrors the cows need to use in order to re-direct the laser to the barn.

 

시작점에서 상하좌우 방향으로 쏠 수 있다.

n개의 펜스가 있다.

펜스에 거울을 설치해서 좌 또는 우로 방향을 바꿀 수 있다.

John이 헛간으로 레이저를 쏘기 위한 거울의 최소개수를 구하시오.

 

입력

The first line of input contains 5 space-separated integers: N,xL,yL,xB,yB, where (xL,yL) is the location of the laser and (xB,yB) is the location of the barn. All coordinates are between 0 and 1,000,000,000.

The next N lines each contain the x and y locations of a fence post, both integers in the range 0…1,000,000,000.

 

첫째 줄에 n, xl, yl, xb, yb가 주어진다. (xl, yl)은 레이저의 시작, (xb, yb)는 도달해야 하는 곳이다.

다음 n개의 줄에 펜스의 위치정보가 주어진다.

 

출력

Please output the minimum number of mirrors needed to direct the laser to the barn, or -1 if this is impossible to do.

헛간에 레이저가 가기 위한 최소거울개수를 구하시오. 불가능하면 -1을 출력하시오.

 

풀이

점들을 배열에 담는다.

points[i]에는 i번째점의 x좌표와 y좌표가 주어지는데, 0번째 점은 시작점, n+1번째 점은 맨 끝점이다.

1 ~ n번째 점은 펜스들의 점이다.

 

int -> vector<int>꼴의 해시맵을 만든다.

점들의 좌표를 해시맵에 담아서, 같은 x좌표를 공유하는 점들의 번호, 같은 y좌표를 공유하는 점들의 번호를 각각 저장한다.

 

sameX[x] = {같은 x좌표들인 점들의 번호...}

각각의 해시맵 속의 모든 배열들을 정렬시킨다. sameX의 배열에는 y좌표기준으로, sameY의 배열에는 x좌표기준으로 정렬한다.

그 뒤, 각각 인접한 노드들간의 간선정보를 만들어서 인접리스트에 저장시키는데, {인접 노드, 방향}의 꼴로 간선을 저장해준다.

 

이제, 시작점에서 0-1 bfs를 시작한다.

최소비용을 담는 costs는 costs[점 번호][방향]의 꼴로 만들고, 큰 수로 초기화시킨다.

그 뒤, costs[0][0~3]은 모두 0으로 해주고, 0-1 bfs를 위한 deque에 추가한다.

 

0-1 bfs를 시행한다. 인접한 노드들에 대해 새로운 비용이 기존의 이웃노드의 비용보다 저럼하면 가는데, 시작점이거나, 방향이 같아서 가중치가 0이라면, dq의 맨 앞에 추가하여, 0으로 연결된 곳을 빠르게 처리하도록 하였다.

 

dist[n+1]의 최소값을 구해서 출력하면 된다. 만약 dist[n+1]이 갱신된 적 없다면, -1을 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
// 0 = LEFT, 1 = RIGHT, 2 = UP, 3 = DOWN

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, xs, ys, xe, ye;
    cin >> n >> xs >> ys >> xe >> ye;

    vector<pii> points;
    points.emplace_back(xs, ys);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        points.emplace_back(x, y);
    }
    points.emplace_back(xe, ye);

    int m = n + 2;
    vector<vector<pii>> adj(m);
    unordered_map<int, vector<int>> sameX, sameY;
    for (int i = 0; i < m; i++) {
        sameY[points[i].second].emplace_back(i);
    }
    for (auto &[k, v] : sameY) {
        sort(v.begin(), v.end(),
             [&](int i, int j) { return points[i].first < points[j].first; });
        for (int i = 1; i < v.size(); i++) {
            int u = v[i - 1], w = v[i];
            adj[u].emplace_back(w, 1);
            adj[w].emplace_back(u, 0);
        }
    }

    for (int i = 0; i < m; i++) {
        sameX[points[i].first].emplace_back(i);
    }
    for (auto &[k, v] : sameX) {
        sort(v.begin(), v.end(),
             [&](int i, int j) { return points[i].second < points[j].second; });
        for (int i = 1; i < v.size(); i++) {
            int u = v[i - 1], w = v[i];
            adj[u].emplace_back(w, 2);
            adj[w].emplace_back(u, 3);
        }
    }

    deque<pii> dq;
    vector<array<int, 4>> dist(m);
    for (int i = 0; i < m; i++) {
        dist[i].fill(1e9);
    }
    for (int d = 0; d < 4; d++) {
        dist[0][d] = 0;
        dq.emplace_back(0, d);
    }

    while (!dq.empty()) {
        int curr, dir;
        tie(curr, dir) = dq.front();
        dq.pop_front();
        int curDist = dist[curr][dir];

        for (auto &elem : adj[curr]) {
            int next = elem.first;
            int nextDir = elem.second;
            if(abs(dir - nextDir) == 1 && !(dir == 1 && nextDir == 2) && !(dir == 2 && nextDir == 1)) continue;

            int weight = (curr == 0 || dir == nextDir) ? 0 : 1;
            if (curDist + weight < dist[next][nextDir]) {
                dist[next][nextDir] = curDist + weight;
                if (weight == 0)
                    dq.emplace_front(next, nextDir);
                else
                    dq.emplace_back(next, nextDir);
            }
        }
    }

    int ans = *min_element(dist[m - 1].begin(), dist[m - 1].end());
    if (ans == 1e9) {
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}