백준 192381 19238. 스타트 택시 (Python) 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 BFS를 활용한 구현 문제다. 처음에는 현재 택시 위치에서 모든 승객들에 대한 거리를 구해서 최소 힙에 넣어두고 문제에 주어진 조건에 따라서 먼저 태워야 하는 손님을 찾도록 구현했다. 그러다보니 매번 손님과 모든 남은 승객들의 거리를 구해야했고 아마 이 때문에 시간 초과가 발생한 것으로 보인다. 그래서 현재 택시 위치에서 BFS 탐색을 시작하여 가장 먼저 만나게 되는 승객을 찾도록 변경하였다. 위의 그림은 문제에서 주어.. 2022. 7. 13. 이전 1 다음
