[백준] 버스 갈아타기

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

2536번: 버스 갈아타기

BFS를 이용하는 문제입니다. 

 

문제부터 간단하게 요약하면, 버스들이 

그림 처럼 생긴 좌표들 위를 움직이는데, 가로축 혹은 세로축으로 움직입니다. 각각의 버스들이 노선을 가질 때, 주어진 출발지에서 도착지로 도착하는데 최소한으로 이용해야 하는 버스 갯수를 구하는 문제입니다.

 

<Solution>

BFS를 이용해야 합니다. 

 

로직을 생각해 봅시다. 

1. 출발 지점을 지나는 버스들을 탑승 표시를 하고 queue에 넣는다. 2. queue가 빌 때까지 while 문을 돌린다. 2-1. while문에서는 해당하는 pop된 버스와 노선이 겹치면서, 이미 탑승하지 않은 버스를 탑승한다. 2-2. 이 때, 만약 탑승하는 버스가 도착지점을 지나면 return 2-3. 만약 도착지점을 지나지 않는다면, 탑승표시하고 queue에 넣어준다.

이렇게 BFS를 하면 된다는 것을 알 수 있습니다. 

 

이 때, 생각 해보아야 하는 문제들이 있습니다. 저의 경우 row 방향으로 움직이는 bus들과 column 방향의 bus들을 별개로 관리해 주었습니다. 

bus r_bus[5000+10];
bus c_bus[5000+10];

 

왜 이렇게 다르게 생각을 해주는지 생각해보면, 

우리는 매 상황을 4가지로 나누어 생각할 수 있습니다.

 

1. queue에서 pop한 bus가 row방향으로 움직일 때
	1-1. 새로운 bus가 column 방향으로 겹칠 때
	1-2. 새로운 bus가 row 방향으로 겹칠 때
2. queue에서 pop한 bus가 column 방향으로 움직일 때
	2-1. 새로운 bus가 row 방향으로 겹칠 때
	2-2. 새로운 bus가 column 방향으로 겹칠 때

이렇게 우리는 4가지 경우를 생각할 수 있습니다. 

 

그림으로 표현하면, 

각각의 경우들은 다음과 같이 표현이 됩니다.

 

이 경우들을 나누어 구현을 하기 위해 r_bus와 c_bus를 따로 관리해주는 것을 알 수 있습니다.

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <queue>
#include <utility>

using namespace std;
int M, N, K;

struct bus{
    int id;
    int sr, sc, er, ec;
    int type; // 0 row 1 column bus
};

int used[5000+10]; // memorize by id
bus r_bus[5000+10];
bus c_bus[5000+10];
int cnt_rbus, cnt_cbus;

int sr, sc, er, ec;

void getinput(){
    cin >> M >> N >> K; // column, row, number of bus
    int tmpc, tmpr, tmpc_, tmpr_;
    int id;
    // row bus, column bus 따로 기록
    // 2,5 -> 2,1 이런 경우 2,1 -> 2,5로 재졍렬
    for(int i = 0; i<K; i++){
        cin >>id >> tmpc >> tmpr >> tmpc_ >> tmpr_;

        if(tmpr == tmpr_){ // row bus임 (row 방향으로 움직임)
            r_bus[cnt_rbus].sr = tmpr;
            r_bus[cnt_rbus].er = tmpr;
            if(tmpc>tmpc_){
                r_bus[cnt_rbus].sc = tmpc_;
                r_bus[cnt_rbus].ec = tmpc;
            }
            else{
                r_bus[cnt_rbus].sc = tmpc;
                r_bus[cnt_rbus].ec = tmpc_;
            }
            r_bus[cnt_rbus].type = 0;
            r_bus[cnt_rbus].id = id;
            cnt_rbus++;
        }
        else{ // column bus임 
            c_bus[cnt_cbus].sc = tmpc;
            c_bus[cnt_cbus].ec = tmpc;
            if(tmpr>tmpr_){
                c_bus[cnt_cbus].sr = tmpr_;
                c_bus[cnt_cbus].er = tmpr;
            }
            else{
                c_bus[cnt_cbus].sr = tmpr;
                c_bus[cnt_cbus].er = tmpr_;
            }
            c_bus[cnt_cbus].type = 1;
            c_bus[cnt_cbus].id = id;
            cnt_cbus++;
        }
    }

    // get start, end points
    cin >> sc >> sr >> ec >> er;
}

int solution(){

    // sort buses
    // column방향의 bus는 row기준 정렬
    // row 방향의 bus는 column기준 정렬
    // 이진 탐색 굳이 안할꺼라 패스

    // find start bus and add to queue
    queue <pair<bus, int>> q; // int is used for cnt

    for(int i = 0; i<cnt_rbus; i++){
        if(r_bus[i].sr == sr && r_bus[i].sc <=sc && r_bus[i].ec >= sc){
            if(r_bus[i].sr == er && r_bus[i].sc <= ec && ec <= r_bus[i].ec) return 1;
            q.push({r_bus[i],1});
            // visited
            used[r_bus[i].id] = 1;
        }
    }
    for(int i = 0; i<cnt_cbus; i++){
        if(c_bus[i].sc == sc && c_bus[i].sr <= sr && c_bus[i].er >= sr ){
            if(c_bus[i].sc == ec && c_bus[i].sr <= er && c_bus[i].er >= er) return 1;
            q.push({c_bus[i],1});
            // visited
            used[c_bus[i].id] = 1;
        }
    }

    while(!q.empty()){
        pair<bus,int> cur = q.front(); q.pop();

        //if row bus
        if(cur.first.type == 0){
            for(int i = 0; i<cnt_cbus; i++){
                // if already used skip
                if(used[c_bus[i].id] == 1) continue;

                // if it is in range-> mark visited and enqueue
                if(c_bus[i].sr <= cur.first.sr && c_bus[i].er >= cur.first.sr && c_bus[i].sc >= cur.first.sc && c_bus[i].sc <= cur.first.ec){

                    // if there is end point return
                    if(c_bus[i].sc == ec && c_bus[i].sr <= er && c_bus[i].er >= er) return cur.second+1;
                    used[c_bus[i].id] = 1;
                    q.push({c_bus[i], cur.second+1});

                }
            }
            // if there is another row bus
            for(int i = 0; i<cnt_rbus; i++){
                // if already used skip
                if(used[r_bus[i].id] == 1) continue;

                // if it is in range-> mark visited and enqueue
                if(r_bus[i].sr == cur.first.sr && ((r_bus[i].sc >=cur.first.sc && r_bus[i].sc <= cur.first.ec) || (r_bus[i].ec >= cur.first.sc && r_bus[i].ec <= cur.first.ec))){
                    if(r_bus[i].sr == er && r_bus[i].sc <= ec && ec <= r_bus[i].ec) return cur.second +1;
                    used[r_bus[i].id] = 1;
                    q.push({r_bus[i], cur.second+1});
                }
            }
        }
        // if column bus
        else{
            for(int i = 0; i<cnt_rbus; i++){
                //if already used skip
                if(used[r_bus[i].id] == 1) continue;
                // if it is in range-> mark visited and enqueue
                if(r_bus[i].sc <= cur.first.sc && cur.first.sc <= r_bus[i].ec && cur.first.sr <= r_bus[i].sr && r_bus[i].sr <= cur.first.er){

                    // if there is end point return
                    if(r_bus[i].sr == er && r_bus[i].sc <= ec && ec <= r_bus[i].ec) return cur.second +1;
                    used[r_bus[i].id] = 1;
                    q.push({r_bus[i], cur.second+1});
                }
            }
            // if there is another column bus
            for(int i = 0; i<cnt_cbus; i++){
                // if already used skip
                if(used[c_bus[i].id] == 1) continue;

                // if it is in range-> mark visited and enqueue
                if(c_bus[i].sc == cur.first.sc && ((c_bus[i].sr >=cur.first.sr && c_bus[i].sr <= cur.first.er) || (c_bus[i].er >= cur.first.sr && c_bus[i].er <= cur.first.er))){
                    if(c_bus[i].sc == ec && c_bus[i].sr <= er && c_bus[i].er >= er) return cur.second+1;
                    used[c_bus[i].id] = 1;
                    q.push({c_bus[i], cur.second+1});
                }
            }

        }

    }
    // never reach
    return -1;
}

int main(){

    getinput();

    int ans = solution();

    cout << ans << endl;
    return 0;

}