[BOJ]백준 19238번: 스타트 택시 풀이/코드/반례
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
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