[백준] 19238.스타트 택시 (Swift)

[백준] 19238.스타트 택시 (Swift)

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

풀이

BFS 를 이용한 최단거리 계산 문제입니다.

 

같은 거리에 있는 승객이 여러명이라면 행의 크기가 가장 작은 승객을, 그마저도 여러명이라면 열의 크기가 가장 작은 승객을 태우는 것이 문제의 조건입니다.

 

이를 해결하기 위해서 먼저 BFS 로 모든 승객과의 거리를 계산한 후에 최소거리에 있는 승객을 추려냈습니다. 이후 행과 열의 크기를 비교해주는 방식으로 진행했습니다.

 

승객과 도착지 정보는 Dictionary 를 이용하여 1:1 대응이 될 수 있도록 하였습니다.

 

택시가 이동할때 계속해서 연료 상태를 확인하여 연료가 다 떨어진다면 문제를 종료할 수 있도록 하였습니다.

코드

 

코드에서 사용되는 Queue 자료구조의 구현은 아래 링크에서 확인하실 수 있습니다.

https://trumanfromkorea.tistory.com/37

[자료구조] Swift 로 Queue 구현하기