[백준] No.10165 - 버스 노선 (C++)

문제

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

10165번: 버스 노선

 

풀이

 

solved.ac 난이도: Platium 5

 

정렬을 해서 푸는 것까지는 생각해냈지만 0을 지나는 노선의 처리하지 못하여 틀린 그리디 문제.

 

해당 문제는 0을 지나지 않는 노선(line_v)와  0을 지나는 노선(cross_line_v)로 나누어 해결해야 한다.

 

1. 0을 지나지 않는 노선(line_v)

 

해당 노선들은 시작점(start)을 기준으로 오름차순 정렬, 만약 시작점이 같다면 끝점(end)을 기준으로 내림차순 정렬을 해준다.

이렇게 하면 앞의 노선은 항상 뒤의 노선들보다 먼저 시작한다.

따라서 뒤의 노선이 앞의 노선을 포함할 수 없다. 반대로 앞의 노선은 뒤의 노선을 포함할 가능성을 갖는다.

만약 시작점이 같은 경우에도 뒤의 노선이 끝점이 더 작기 때문에 앞의 노선을 포함할 수 없다.

 

max_end(지나온 노선중 가장 end가 큰 점)를 통해 현재 노선의 끝점(now_end)과 비교하여 

now_end <= max_end 라면 현재 노선은 앞의 특정 노선에 포함이 된다.(앞의 노선은 항상 start가 크기 때문)

 

2. 0을 지나는 노선(cross_line_v)

0을 지나는 노선끼리는 위의 1번과 같은 루틴으로 포함관계를 알 수 있다.

 

3. 0을 지나는 노선과 지나지 않는 노선

0을 지나는 노선은 지나지 않는 노선에 포함될 수 없다. (ex. 9 1 은 그 어떤 일반 노선에 포함될 수 없음)

하지만 반대는 가능하다.

이를 찾아내기 위해서는 cross_line_v의 가장 작은 시작점(min_start)과 가장 큰 끝점(max_end)을 알아야 한다.

 

예를 들어 아래와 같은 예제를 보자.

line_v

0 2

3 4

 

cross_line_v

4 0 -> (min_start = 4)

5 2 -> (max_end = 2)

 

 

line_v의 시작 점이 min_start보다 크거나 같다면, line_v의 끝점은 항상 bus_stop_num-1 이하 이기 때문에 min_start를 가지는 cross_line_v의 노선에 포함될 수밖에 없다.

 

또한 line_v의 끝점이 max_end보다 작거나 같다면, line_v의 시작점은 항상 0 이상이기 때문에 max_end를 가지는 cross_line_v의 노선에 포함될 수밖에 없다.

 

해당 코드의 구현에 있어서 각각의 버스 노선의 시작점, 끝점, 노선 번호를 저장해야 했기 때문에 pair만으로는 부족했다.

따라서 아래와 같은 struct를 직접 구현하여 사용하였다. sort에 필요한 연산자 오버 로딩도 구현해주면 편리하다.

 

struct bus_line_info{
  int start,end,line_number;
  bus_line_info(int s, int e, int n): start(s), end(e), line_number(n){}
 
  bool operator<(bus_line_info& ret){    
    if(start == ret.start)      
    return end > ret.end;    
  return start < ret.start;
  }
};

 

일단 정렬을 하면 한 번의 순회로 값을 찾을 수 있는 스위핑 기법이 사용되기 때문에 복잡도는 O(MlogM)이다.

코드