[백준 19238] 스타트 택시 (C++)

A. 문제설명

www.acmicpc.net/problem/19238

19238번: 스타트 택시

문제에 대한 자세한 설명은 링크 참조

 

1. 아래와 같은 N*N 배열판이 존재(흰색이 빈칸, 회색이 벽)

2. 택시 운전자가 M명의 승객을 각각의 목적지에 데려다 주려함

3. M명의 승객들 중, 태울 손님을 고르는 기준은 가장 최단거리, 만약 최단거리인 손님이 여러명이면 최상위 행을 우선으로, 그래도 여러명이면 최좌측 열을 우선으로 선택

4. M명의 승객은 동시에 여러명이 탑승할 수는 없음

5. 연료는 한 칸을 이동할 때마다 1 소모되며, 택시는 승객을 태운 시점부터 목적지에 도달시키면, 2 * |승객의 위치에서 목적지까지의 거리| 만큼의 연료를 돌려받음

6. 이동 중 연료가 모두 소모되면 그날 영업은 실패로 돌아감

7. 모든 승객을 이동시키고 남은 연료의 양을 구하라

 

B. 접근법

정렬 + BFS

 

스타트 택시 문제의 핵심을 하나씩 짚어보자.

1. 택시 운전자는 현재의 위치에서 가장 최단거리에 있는 손님을 태워야 함

매 반복마다 택시 운전자의 위치에서 손님간의 거리를 모두 구해 정렬한다.

정렬의 비용은 생각보다 비싸지 않다. 손님을 한명씩 태울 때마다 큐에서 빼기 때문에 전체 수행의 수는 n부터 1로 줄어드는 경우의 수로 모두 $n(n+1)/2$ 이며, 정렬의 비용은 $O(nlogn)$이다.

bool cmp_user(USER &u1, USER &u2){
  if(u1.dist == u2.dist && u1.x == u2.x) return u1.y < u2.y;
  else if(u1.dist == u2.dist) return u1.x < u2.x;
  else return u1.dist < u2.dist;
}

int start_taxi(){
	...
    for (int j = 0; j < userVec.size(); j++) userVec[j].dist = get_taxi_dist_bfs(j);
    sort(userVec.begin(), userVec.end(), cmp_user);

정렬의 기준은 위 cmp_user() 함수의 구현과 같이, 택시와 손님간의 거리 - 손님의 행 번호(낮은 번호 우선) - 손님의 열 번호(낮은 번호 우선) 순이다.

 

2. 연료는 손님을 태우러 갈 때, 손님을 태운 후 목적지로 이동할 때 소모되며 목적지에 도달시 손님 위치에서 목적지까지의 거리의 두배를 보상받음

여기서, 매 반복마다 '손님까지의 거리 + 손님위치에서 목적지까지의 거리 > 잔여연료량'를 검사하며 도달 시 '잔여연료량 = 잔여연료량 - 손님까지의 거리 + 손님위치에서 목적지까지의 거리'로 계산해주었다.

// 잔여 연료량 체크해서 나머지 목적지까지 도달 못하면 -1 반환
if(userVec.front().dist + userVec.front().dest > Fuel) return -1;
else if(userVec.front().dist == -1) return -1; // 반례: 도달 불가능한 목적지가 하나라도 있다면 완전한 택시영업 불가능

위 조건식은 start_taxi() 함수의 구현부 94번째 라인이다.

 

3. 지도는 벽과 빈칸으로 구성되어 일반적인 2차원 좌표평면상 두 거리를 구하면 안되고 매번 새로운 위치에서 탐사하며 직접 택시와 손님간의 거리를 구해야 함

손님과 택시간의 거리, 손님과 목적지의 거리 탐사는 BFS로 구하도록 한다. 탐사시, 벽을 피해가며 목적지 발견시 바로 종료하도록 구현하였다.

D에 공유된 코드에 get_dest_bfs()/get_taxi_dist_bfs() 두 함수가 이에 해당한다.

 

C. 풀이

1. 각 손님의 위치에서부터 목적지까지의 거리를 미리 계산

2. BFS로 택시 to 시민거리 모두 구함

3. 택시-시민거리, 행번호, 열번호 순으로 정렬

4. 잔여 연료량 체크해서 나머지 목적지까지 도달 못하면 -1 반환

5. 도달 불가능한 목적지가 하나라도 있다면 완전한 택시영업 불가능으로 -1 반환

6. 도달 가능하면 잔여연료량 업데이트 후 나머지 순회 2부터 다시 반복

7. 모든 승객 이동 후 잔여 연료량 반환

 

D. 내 코드