[BOJ] 백준 2536 버스 갈아타기

출처: https://www.acmicpc.net/problem/2536

 Input 

7 6

8

1 2 1 2 2

2 1 1 5 1

6 7 3 7 6

7 2 1 2 6

3 3 2 6 2

4 5 6 5 1

5 1 5 7 5

8 3 5 6 5

2 1 7 4

　 

 Output 

3

① BFS탐색하기 위해서 Queue에 출발지에서 승차할 수 있는 버스 번호를 저장합니다.

    수평[idx] = idx번째에서 수평으로 이동하는 버스 번호를 저장합니다.

    수직[idx] = idx번째에서 수직으로 이동하는 버스 번호를 저장합니다.

② BFS 탐색은 크게 2가지 방향으로 진행됩니다.

    - 수평(ㅡ)으로 이동하는 버스

    - 수직( | )으로 이동하는 버스

③ 수평으로 이동한다고 했을 때, x 좌표가 동일합니다.

    해당 위치들에서 탈 수 있는 버스를 다시 BFS 탐색

④ 수직으로 이동하는 경우 y좌표가 동일합니다.

    해당 위치들에서 탈 수 있는 버스를 다시 BFS 탐색

ex) 출발선상에서 탈 수 있는 버스를 모두 승차합니다. (BFS 1단계)

      내릴 수 있는 곳에서 환승가능한 버스가 있다면 환승합니다.

      이때, 기존에 탑승한 버스를 다시 탑승할 필요 없으며, 앞서 보다 빠르게 환승한 경로이며 시도하지 않습니다.

      즉, visited[]로 가장 빠르게 탑승한 경우 저장합니다.

* 버스 노선이 끝과 끝이 아닌 일부 구간일 수 있습니다.

* 주어지는 input의 크기와 방향을 제각각입니다.

---

#include <stdio.h>
 
const int MAX_BUS = 5000 + 5;
const int MAX_NM = 100000 + 5;
inline void swap(int& A, int& B) { int temp = A; A = B; B = temp; }
 
int M, N, K, visit[MAX_BUS], sx, sy, dx, dy;
struct Bus {
    int x1, y1, x2, y2;
}bus[MAX_BUS];
 
struct Node {
    int s, e, ID;
    Node* next;
    Node* alloc(int _s, int _e, int _ID, Node* _next) {
        s = _s, e = _e, ID = _ID; next = _next;
        return this;
    }
}buf[MAX_BUS], * horizontal[MAX_NM], * vertical[MAX_NM];
int bcnt;
 
struct Queue {
    int fr, re;
    int arr[MAX_BUS * 4];
    void push(int data) {
        arr[re++] = data;
    }
    int pop() {
        return arr[fr++];
    }
}que;
 
int BFS() {
    // 출발 선상 좌표
    // 수직선으로 이동하는 버스
    for (Node* v = vertical[sx]; v; v = v->next) {
        if (sy >= v->s && sy <= v->e) {
            visit[v->ID] = 1;
            que.push(v->ID);
        }
    }
    // 수평선으로 이동하는 버스
    for (Node* v = horizontal[sy]; v; v = v->next) {
        if (sx >= v->s && sx <= v->e) {
            visit[v->ID] = 1;
            que.push(v->ID);
        }
    }
 
    while (que.fr < que.re) {
        int cur = que.pop();
        int x1 = bus[cur].x1, y1 = bus[cur].y1;
        int x2 = bus[cur].x2, y2 = bus[cur].y2;
 
        if (y1 == y2) {
            if (y1 == dy && dx >= x1 && dx <= x2) return visit[cur];
            for (int x = x1; x <= x2; x++)
                for (Node* v = vertical[x]; v; v = v->next) {
                    if (!visit[v->ID] && y1 >= v->s && y1 <= v->e) {
                        visit[v->ID] = visit[cur] + 1;
                        que.push(v->ID);
                    }
                }
            for (Node* v = horizontal[y1]; v; v = v->next) {
                if (!visit[v->ID] && !(x1 > v->e || x2 < v->s)) {
                    visit[v->ID] = visit[cur] + 1;
                    que.push(v->ID);
                }
            }
        }
 
        else {
            if (x1 == dx && dy >= y1 && dy <= y2) return visit[cur];
            for (int y = y1; y <= y2; y++)
                for (Node* v = horizontal[y]; v; v = v->next) {
                    if (!visit[v->ID] && x1 >= v->s && x1 <= v->e) {
                        visit[v->ID] = visit[cur] + 1;
                        que.push(v->ID);
                    }
                }
            for (Node* v = vertical[x1]; v; v = v->next) {
                if (!visit[v->ID] && !(y1 > v->e || y2 < v->s)) {
                    visit[v->ID] = visit[cur] + 1;
                    que.push(v->ID);
                }
            }
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d", &M, &N, &K);
    int ID, x1, y1, x2, y2;
 
    for (int i = 0; i < K; i++) {
        scanf("%d %d %d %d %d", &ID, &x1, &y1, &x2, &y2);
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        if (x1 == x2)
            vertical[x1] = buf[bcnt++].alloc(y1, y2, ID, vertical[x1]);
        else if (y1 == y2)
            horizontal[y1] = buf[bcnt++].alloc(x1, x2, ID, horizontal[y1]);
        bus[ID] = { x1, y1, x2, y2 };
    }
 
    scanf("%d %d %d %d", &sx, &sy, &dx, &dy);
    printf("%d\n", BFS());
}