백준 19238번 스타트 택시

문제 링크입니다: https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

행과 열을 헷갈려서 한참을 틀렸던 문제였습니다.

* 행은 세로 즉 y축, 열은 가로 즉 x축이라는 것을 명심합시다...

 

알고리즘은 아래와 같습니다.

1. 문제의 조건에 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다. 라는 내용이 명시되어 있으므로 map을 선언하여 출발지를 key, 목적지를 value로 입력받습니다. 이렇게 할 경우 a 손님의 목적지와 b 손님의 출발지가 같더라도 쉽게 해결할 수 있습니다.

2. 문제의 조건에 백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 라는 내용이 명시되어 있으므로 {y 좌표, x 좌표, 현재 남아있는 기름 양} 을 저장하는 구조체를 선언하고 조건에 맞게 우선순위 큐를 선언해줍니다.

3. 현재 위치에서 2번에 선언한 우선순위 큐를 이용하여 BFS 알고리즘을 통해 가장 가까운 손님을 찾습니다.

4. 가장 가까운 손님을 찾은 뒤에는 그냥 큐를 이용하여 BFS 알고리즘을 통해 목적지까지 최단 경로를 구합니다.

5. 3 ~ 4번 과정을 M번 반복하고 그 과정 중 기름을 모두 사용한다면 -1을 출력하고 프로그램을 종료하고 M번 반복한 뒤에도 기름이 남아있다면 남아있는 기름 양을 출력해줍니다.

 

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~