19238. 스타트 택시 (백준, 자바)

문제

19238번: 스타트 택시

---

풀이

1. 단순히 테이블 상에서 가장 가까운 손님을 찾는다.

2. 손님의 목적지까지 데려다준다.

손님을 다 태워줄때까지 반복하면 되는 문제이다.

 

BFS를 사용해서 가까운 손님(거리가 같으면 행,열 조건에 맞게 행렬 비교)을 찾고,

목적지까지 태워주는 대신 연료량을 체크하면 되는 문제

 

조건은 간단하나 두가지 문제가 있어 시간이 많이 걸리게 되었다.

 

• 시간초과
• 손님을 목적지까지 바래다 주자마자 다음 손님이 위치해 있는 경우

 

처음 구현할 때 손님별로 목적지까지 미리 계산해버리는 식으로 먼저 구현해버렸기 때문에 시간초과가 났었다.

두번째 문제는 오랫동안 찾지못하고 하나하나 반례를 보면서 문제를 발견하여 해결하였다.

거의 완성시켜버리고 수정하는 식이라 오류를 찾는데 오래걸렸다.

 

다음부터는 작은 단위부터 차례차례 구현하면서 문제를 해결해야겠다.

요새 일정이 너무 힘들어서 잠시 코딩테스트를 보류해두었다가 다시 시작하였는데 벌써부터 감을 잃은 것 같다.

다시 미루지 않고 일주일 5문제를 목표로 차근차근 풀어나가야지

---

코드

GitHub - lyeong-gwa/algorithm_study: 알고리즘 공부!