백준 19238. 스타트 택시

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

19238번: 스타트 택시

 

주어지는 조건을 잘 생각해봐야 하는 문제였다.

조건을 잘 따져보지 않아서 몇번 틀려서 시간이 좀 걸렸다.

 

주어지는 출발지와 도착지에 대한 조건이 다음과 같은데

모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

이 말은 즉 여러개의 목적지들이 같은 좌표일수도 있다라는 뜻이며, 또한 손님1의 도착지와 손님2의 출발지가 같을수도 있다라는 뜻이다.

처음에 이런 조건들을 생각하지 않고 하나의 2차원 배열에 기록했다가 틀렸다.

 

우선 모든 손님들의 출발지 ~ 도착지 까지의 거리를 구해 놓는다.

bfs로 모든 손님들에 대해 구하고 이 중에 도달할수 없는 도착지가 있다면 -1을 출력하고 끝내면 된다.

 

그리고 택시의 위치에서 가장 가까운 손님을 구해야한다.

이때 택시의 위치에 손님이 있는 경우도 고려해줘야 하고, 가장 가까운 손님이 여러명 일 수 있으므로 가장 가까운 손님을 찾아도 바로 bfs를 끝내면 안된다.

 

 

이번 문제도 처음에 조건을 제대로 안따져봐서 금방 풀수 있었는데 시간이 더 걸렸다.

문제를 잘 읽고 조건을 잘 따져보자!