[백준] No.2536 - 버스 갈아타기 (C++, BFS)

문제

 

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

2536번: 버스 갈아타기

 

 

 

풀이

 

solved.ac 난이도: Gold 1

 

풀이를 생각해내는 것은 어렵지 않았지만 구현이 까다로웠던 문제이다.

일단 모든 좌표를 정점으로 만드는 것은 수직선과 수평선이 최대 100,000개이기 때문에 시간 초과는 물론 메모리도 초과해버린다.

하지만 버스의 수는 최대 5000개로 모든 버스를 충분이 정점으로 표현해낼 수 있는 수치이다.

 

따라서 버스들 중에서 서로 운행 선분이 겹치는 버스들은 간선으로 연결해 그래프를 만들어주자.

그 후 시작 위치를 지나는 버스들을 초기 BFS 시작 정점으로, 목적지를 지나는 버스들을 BFS의 종료 정점으로 만들어준다.

이제 시작 정점들을 큐에 넣은 BFS를 진행하여 종료 정점으로의 간선 수(최단 거리 혹은 최단 환승 수)를 구해주면 된다.

 

그래프를 만들 때 모든 버스의 수가 5000을 넘지 않으므로 단순한 2중 반복문으로 서로의 운행 선분이 겹치는지를 확인해 주어도

시간 복잡도는 O(n^2)로 25,000,000을 넘지 않으므로 충분히 그래프를 만들 수 있다.

 

 

이를 구현하기 위해 버스의 정보를 저장하는 구조체 BusInfo를 선언해주었다.

 

struct BusInfo{
  int idx;
  bool is_horizon;
  pair<int,int> start_pos, end_pos;
};

 

bool is_horizon은 해당 버스의 운행 선분이 수평인지의 여부를 저장한다.

그 이유는 다음과 같다.

 

두 개의 선분끼리의 교차점을 찾을 때 상황은 4가지가 존재한다.

 

1. A선분이 수평이고 B선분이 수평
2. A선분이 수직이고 B선분이 수평
3. A선분이 수직이고 B선분이 수직
4. A선분이 수평이고 B선분이 수직

이때 4가지의 상황마다 서로의 교차점을 찾기 위해 확인해봐야 하는 선부의 시작 좌표와 끝 좌표의 조건은 모두 다르다.

따라서 모두 각각 다르게 조건을 확인해주자.

 

 

#include<vector>
#include<iostream>
#include<queue>
using namespace std;
 
struct BusInfo{
  int idx;
  bool is_horizon;
  pair<int,int> start_pos, end_pos;
};
 
int row, column, bus_num;
int start_r, start_c, dest_r, dest_c;
BusInfo buses[5001];
vector<vector<int>> adj;
 
int BFS(){
  vector<int> visited(bus_num+1, -1);
  vector<bool> is_dest(bus_num+1, false);
  queue<int> que;
 
  for(int i =1; i<=bus_num ; ++i){  //시작점을 지나는 라인을 큐 넣어두기
    if(buses[i].is_horizon){  //수평인 경우
      if(buses[i].start_pos.first != start_r ||
       buses[i].start_pos.second > start_c || start_c > buses[i].end_pos.second)
        continue;
    }else{
      if(buses[i].start_pos.second != start_c ||
       buses[i].start_pos.first > start_r || start_r > buses[i].end_pos.first)
        continue;
    }
    que.push(buses[i].idx);
    visited[buses[i].idx] = 1;
  }
 
  for(int i =1; i<=bus_num ; ++i){  //도착점을 지나는 라인은 표시해주자
    if(buses[i].is_horizon){  //수평인 경우
      if(buses[i].start_pos.first == dest_r &&
       buses[i].start_pos.second <=dest_c &&dest_c<= buses[i].end_pos.second)
        is_dest[buses[i].idx] = true;
    }else{
      if(buses[i].start_pos.second ==dest_c &&
       buses[i].start_pos.first <= dest_r && dest_r<= buses[i].end_pos.first)
        is_dest[buses[i].idx] = true;
    }
  }
 
  int bus_idx,transfer_num , min_transfer;
  while(!que.empty()){
    bus_idx = que.front();
    que.pop();
    transfer_num = visited[bus_idx];
 
    if(is_dest[bus_idx]){
      min_transfer = transfer_num;
      break;
    }
 
    int next_bus;
    for(int i=0; i<adj[bus_idx].size() ; ++i){
      next_bus = adj[bus_idx][i];
      if(visited[next_bus] == -1){
        que.push(next_bus);
        visited[next_bus] = transfer_num +1;
      }
    }
  }
 
  return min_transfer;
}
 
int main(){
  ios_base::sync_with_stdio(0);
  cin>>row>>column>>bus_num;
  adj = vector<vector<int>>(bus_num+1);
 
  int bus_idx, r1, r2, c1, c2;
  for(int i=1; i<=bus_num ; ++i){
    cin>>bus_idx>>c1>>r1>>c2>>r2;
    buses[i].idx = bus_idx;
 
    if(r1 == r2)
      buses[i].is_horizon = true;
    else
      buses[i].is_horizon = false;
 
    if(r1> r2 || c1 > c2){
      buses[i].start_pos = make_pair(r2, c2); 
      buses[i].end_pos = make_pair(r1, c1);
    }else{
      buses[i].start_pos = make_pair(r1, c1); 
      buses[i].end_pos = make_pair(r2, c2);
    }
 
 
    BusInfo& now_bus = buses[i], comp_bus;
    for(int j=1; j<i ; ++j){
      comp_bus = buses[j];
      
      if(comp_bus.is_horizon == now_bus.is_horizon){ //같은 방향
        if(now_bus.is_horizon){ //지금 버스 라인이 수평인 경우
          if( now_bus.start_pos.first != comp_bus.start_pos.first || //같은 수평선에 있는지
          comp_bus.end_pos.second < now_bus.start_pos.second || now_bus.end_pos.second < comp_bus.start_pos.second  )
            continue;
        }else{
          if( now_bus.start_pos.second != comp_bus.start_pos.second || //같은 수직선에 있는지
          comp_bus.end_pos.first < now_bus.start_pos.first || now_bus.end_pos.first < comp_bus.start_pos.first  )
            continue;
        }
 
      }else{  //다른 방향
        if(now_bus.is_horizon){ //지금 버스 라인이 수평인 경우
          if((now_bus.start_pos.first < comp_bus.start_pos.first || comp_bus.end_pos.first < now_bus.start_pos.first) ||
           (comp_bus.start_pos.second < now_bus.start_pos.second ||  now_bus.end_pos.second < comp_bus.start_pos.second))
            continue;
        }else{
          if((comp_bus.start_pos.first < now_bus.start_pos.first || now_bus.end_pos.first < comp_bus.start_pos.first) ||
           (now_bus.start_pos.second < comp_bus.start_pos.second ||  comp_bus.end_pos.second < now_bus.start_pos.second))
            continue;
        }
      }
 
      adj[now_bus.idx].push_back(comp_bus.idx);
      adj[comp_bus.idx].push_back(now_bus.idx);
    }
 
  }
 
  cin>>start_c>>start_r>>dest_c>>dest_r;
 
  cout<<BFS()<<"\n";
 
  return 0;
}

 

하지만 만족하는 조건을 찾기 위해 OR연산자를 너무 남발하여 읽기 어려운 코드가 되어버렸다..

코드를 작성한 본인도 읽기 어려워 오류를 찾는데도 한참 걸렸다...

이런 한심한 코드를 해석하는 것보다는 직접 조건을 세워보는 것을 추천드립니다...

 

 

코드