BOJ 2536 버스 갈아타기

사용한 알고리즘

다익스트라

알고리즘 설명

N, M의 값이 최대 10만이므로 좌표로 접근해서 풀기는 어렵다는 생각이 들었다.
버스의 수 K 값이 5000 인 점을 이용하고자 하였다.
시작점을 0, 버스를 1~K, 도착점을 K+1 로 정하여 component에 저장하였다.
이후 이 각각 선분들이 겹치는 지를 판단하고, 만약 겹친다면 그래프를 연결하였다.
모든 연결은 O(N^2)으로 가능하고 이후 0에서부터 K+1 까지 최단거리를 계산한다.
마지막에 도착할때에 더해지는 +1를 상쇠하기 위해서 -1를 한 값을 출력한다.

풀이

// baekjoon 2536 yechan
#include <bits/stdc++.h>
using namespace std;
using P = pair<int,int>;
using PP = pair<P,P>;

const int MAX_N=100001;
const int MAX_K=5002;
const int MAX_INF=1e9;

int N, M, K;
vector<int> adj[MAX_K];
PP component[MAX_K];

int dist[MAX_K];
bool visited[MAX_K];

bool cross(int a, int b) {
    int ax1 = component[a].first.first;
    int ay1 = component[a].first.second;
    int ax2 = component[a].second.first;
    int ay2 = component[a].second.second;

    int bx1 = component[b].first.first;
    int by1 = component[b].first.second;
    int bx2 = component[b].second.first;
    int by2 = component[b].second.second;

    // is overlap x cordinate
    if ( (ax1 <= bx1 && bx1 <= ax2) || (ax1 <= bx2 && bx2 <= ax2) ||
         (bx1 <= ax1 && ax1 <= bx2) || (bx1 <= ax2 && ax2 <= bx2) ) {
        // is overlap y cordinate
        if ( (ay1 <= by1 && by1 <= ay2) || (ay1 <= by2 && by2 <= ay2) ||
             (by1 <= ay1 && ay1 <= by2) || (by1 <= ay2 && ay2 <= by2) ) {
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i=1; i<=K; i++) {
        int num, x1, y1, x2, y2;
        scanf("%d%d%d%d%d", &num, &x1, &y1, &x2, &y2);
        component[num] = PP(P(min(x1,x2),min(y1,y2)),P(max(x1,x2),max(y1,y2)));
    }
    int sx, sy, dx, dy;
    scanf("%d%d%d%d", &sx, &sy, &dx, &dy);
    component[0] = PP(P(sx,sy),P(sx,sy));
    component[K+1] = PP(P(dx,dy),P(dx,dy));
    for (int i=0; i<=K+1; i++) {
        for (int j=i+1; j<=K+1; j++) {
            if (cross(i, j)) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    fill(dist, dist+MAX_K, MAX_INF);
    dist[0] = 0;
    priority_queue<P, vector<P>, greater<P> > PQ;
    PQ.push(P(0, 0));
    while (!PQ.empty()) {
        int curr;
        do {
            curr = PQ.top().second;
            PQ.pop();
        } while (!PQ.empty() && visited[curr]);
        if (visited[curr]) break;

        visited[curr] = true;
        for (int nx: adj[curr]){
            if (dist[nx] > dist[curr] + 1) {
                dist[nx] = dist[curr] + 1;
                PQ.push(P(dist[nx], nx));
            }
        }
    }
    printf("%d\n", dist[K+1]-1);
    return 0;
}