[BOJ] 19238 스타트 택시 (C/C++)

19238번: 스타트 택시

---

오랜만이라 반가운 BFS 문제였다. 문제는 복잡하거나 구현할 것이 많다거나 하지는 않았다. 택시가 동시에 여러 명을 태우고 다녔으면 그건 좀 골치 아팠을 것 같다. 하지만 이 문제는 택시에 한 번에 한 명밖에 태울 수 없기 때문에 그리디하게 풀면 되는 문제였다.

 

택시의 운행 알고리즘은 엄청 심플하다.

1	현재 택시 위치에서 가장 가까운 승객을 찾는다.
2	그 승객을 태우고 도착점까지 최단 거리로 운행한다.

이 과정에서 연료가 다 떨어지면 택시는 더 이상 운행할 수 없다. 1번과 2번에서 최단 거리를 찾기 위해서 BFS를 사용했다. 

 

처음에는 입력을 받을 때 각 승객마다 필요한 운행 거리를 미리 구해놨었다. 만약 승객이 택시를 여러번 탄다면 의미 있는 행동이었겠지만 이 문제에서는 승객이 택시를 한 번만 타고 제외되므로 오히려 lazy하게 거리를 구하는 것이 오버헤드를 줄일 수 있는 방법이었다. 

 

또한, 이 문제에서 이동할 수 없는 벽이 1로 주어진다. 나 같은 경우엔 좌표 상의 0보다 큰 숫자를 해당 좌표에 있는 승객의 번호로 사용했기 때문에 벽을 1이 아니라 -1로 사용했다. 

 

운행을 완료하기 위해서는 승객을 태우러 가는 동안의 연료와 승객을 태우고 도착점까지 가는 동안의 연료가 필요하다. 만약 현재 연료가 그보다 부족하다면 flag를 set하고 -1을 출력했다. 

 

문제에 예시로 주어진 입력 중에 마지막은 아예 지도가 반으로 갈라진 상태이다. 따라서 이동할 수 없음을 나타내는 무한한 값이 필요해서 해당 값을 987654321으로 사용했다.

 

그리고 이 문제에서는 최단 거리가 같은 승객끼리의 우선 순위가 정해져있다. 처음엔 따로 처리를 해주지 않고도 처음에 찾은 승객을 무조건 탑승시킬 수 있도록 할 수 있을 것 같았다. 그런데 잘 되지 않아서 따로 우선 순위를 처리하고 정답을 받았다. 이후에 다른 분들의 코드를 살펴봤을 때에는 딱히 뾰족한 수가 없어보였다.

 

 

 

후기)

오랜만에 좌표 상에서 최단 거리 문제를 풀라고하니까 바로 BFS가 떠오르지 않았다. 처음엔 DFS로 시도하다가 갑자기 생각나서 방법을 바꿨다... 그나마 다행인 점은 구현하는 데 있어서 실수를 하지는 않았다.