백준 BOJ 2536 버스 갈아타기

시도1 .

현재위치 cx,cy를 큐에 넣고

이 위치를 지나가는 버스를 큐를 pop 할때마다 탐색하여 

타지않은 버스를 타고 그 버스의 경로에 뿌리며 큐에 넣는 방법은

 

시간초과

 

 

시도2.

버스의 경로를 보고 교차점이 존재하면 서로 연결된 노드로 판단한다. ( 5000 * 5000 ) 

- 가로 가로  , 가로 세로 , 세로 가로, 세로 세로  4가지 케이스로 나누어서 판단.

 

bfs 탐색

 

시간과 메모리가 조금 크긴한데 통과하였다.

 

 

 

 

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<cmath>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
int n, m, k;
 
struct BUS {
    int sx, sy, ex, ey;
};
struct POSI {
    int num, cnt;
};
 
bool chk[5001];
BUS bus[5001];
vector<int> v[5001];
int sx,sy,dx, dy;
int ans;
 
bool range(int x1, int x2, int y1, int y2) {
    if (x1 <= y1 && y2 <= x2) return true;
    if (y1 <= x1 && x2 <= y2) return true;
    if (x1 <= y1 && y1 <= x2) return true;
    if (x1 <= y2 && y2 <= x2) return true;
    return false;
}
 
void bfs(int cur) {
    queue<POSI> q;
    q.push({ cur,1 });
    chk[cur] = true;
 
    while (!q.empty()) {
        POSI cur = q.front(); q.pop();
 
        int nn = cur.num;
 
        if (bus[nn].sx == bus[nn].ex) {
            if (bus[nn].sx == dx && bus[nn].sy <= dy && dy <= bus[nn].ey) {
                ans = min(ans,cur.cnt);
                break;
            }
        }
        else {
            if (bus[nn].sy == dy && bus[nn].sx <= dx && dx <= bus[nn].ex) {
                ans = min(ans, cur.cnt);
                break;
            }
        }
 
        for (int i = 0; i < v[nn].size(); i++) {
            if (chk[v[nn][i]]) continue;
            chk[v[nn][i]] = true;
            q.push({ v[nn][i], cur.cnt + 1 });
        }
 
 
    }
 
 
}
 
 
int main() {
    scanf("%d %d %d", &m, &n, &k);
 
    for (int i = 0; i < k; i++) {
        int a, b, c, d, e;
        scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
        bus[a].sx = min(b,d); 
        bus[a].sy = min(c,e); 
        bus[a].ex = max(b,d); 
        bus[a].ey = max(c,e);
    }
    
    for (int i = 1; i < k; i++) {
        for (int j = i + 1; j <= k; j++) {
            if (bus[i].sy == bus[i].ey) {
                if (bus[j].sy == bus[j].ey) { 
                    if (bus[i].sy == bus[j].sy && range(bus[i].sx, bus[i].ex, bus[j].sx, bus[j].ex)) {
                        v[i].push_back(j);
                        v[j].push_back(i);
                    }
                }
                else {
                    int mm = bus[j].sy;
                    int mmm = bus[j].ey;
                    if (bus[i].sx <= bus[j].sx && bus[j].sx <= bus[i].ex && mm <= bus[i].sy && bus[i].sy <= mmm) {
                        v[i].push_back(j);
                        v[j].push_back(i);
                    }
                    
                }
 
            }
            else if (bus[i].sx == bus[i].ex) {
                if (bus[j].sx == bus[j].ex) {
                    if (bus[i].sx == bus[j].sx && range(bus[i].sy, bus[i].ey,bus[j].sy, bus[j].ey)) {
                        v[i].push_back(j);
                        v[j].push_back(i);
                    }
                }
                else {
                    int mm = bus[j].sx;
                    int mmm = bus[j].ex;
                    if (bus[i].sy <= bus[j].sy && bus[j].sy<=bus[i].ey && mm <= bus[i].sx && bus[i].sx <= mmm) {
                        v[i].push_back(j);
                        v[j].push_back(i);
                    }
 
                }
 
            }
        }
    }
    
 
    scanf("%d %d %d %d", &sx, &sy, &dx, &dy);
 
    
    ans = INF;
    for (int i = 1; i <= k; i++) {
        memset(chk, false, sizeof(chk));
        if (bus[i].sx == bus[i].ex) {
            if (bus[i].sx == sx && bus[i].sy <= sy && sy <= bus[i].ey) {
                bfs(i);
            }
        }
        else {
            if (bus[i].sy == sy && bus[i].sx <= sx && sx <= bus[i].ex) {
                bfs(i);
            }
        }
    }
 
    printf("%d", ans);
 
 
    return 0;
}