[BOJ]백준 19238번: 스타트 택시 풀이/코드/반례

www.acmicpc.net/problem/19238

19238번: 스타트 택시

BFS응용문제인 스타트 택시 문제이당

택시는 지정된 위치에서 출발하고, 현재 가장 가까운 위지에 있는 승객에게로 가서 태운 뒤 해당 승객의 목적지로 간다

위의 과정을 모든 승객에 대해 전부 반복하면서, 남아있는 연료의 양을 계산하는 문제

위와 같은 그림에서는

2번 승객(거리: 6)를 태우면, 연료는 15-6=9가 된다

2번 승객의 목적지인 (1,6)으로 가면 연료를 6소모하는데, 12만큼 채우니까 연료는 9-6+6*2 = 15

 

이러한 과정을 반복하면서, 주의해야 할 것은

1️⃣ 출발지 or 목적지가 벽으로 막혀있을 경우

2️⃣ 가는 도중!!에 연료가 바닥날 경우

두 가지 경우에 대해서 -1을 출력하도록 해주면 된다

 

나는 1부터 시작하는 인덱스 번호를 0으로 바꿔주는 과정에서 오류가 있었어서 4트만에 풀었다 ㅠㅡㅜ

똑같은 실수 반복하지 않도록 주의하자

위 같은 두 함수를 선언해서 승객에게 갈 때, 목적지로 갈 때를 구분해줬는데 사실 BFS 뼈대는 같아서 한 함수로 통일해줘도 된다

 

반례 모음

 

6 4 15

0 0 1 0 0 0

0 0 1 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 1 0

0 0 0 1 0 0

6 5

2 2 5 6

5 4 1 6

4 2 3 5

1 6 5 4

답 : 20

 

3 2 4
0 1 0 
0 1 0
1 0 0
3 3
3 2 1 3
1 3 3 3

답: 8