pepper_mis   7달 전

사이클이 될까봐 특정목적지 까지의 최소시간과 최소시간에 드는 비용을 저장해두고 시간이 더 걸리면서 비용도 더 큰 경우는 제외되도록 만들었습니다.

마지막에 여기에서 N에 해당하는 최소시간을 출력하도록 만들었어요.

12퍼센트가 되자마자 시간초과가 뜨는데, 어떤 경우에 오래걸리는 걸까요?

djm03178   7달 전

BFS의 전제조건은 '모든 간선의 가중치가 동일해야 한다'입니다. 이 문제와 같이 간선의 가중치가 여러 종류가 나올 수 있는 경우 거리가 갱신될 때마다 큐에 원소를 넣으면 중복된 원소가 들어가기 때문에 비효율적이고, 최악의 경우에는 O((비용의 최댓값)*(정점의 개수))의 시간이 걸리게 됩니다. 이 문제는 다익스트라로 풀어야 하고, 그 중에서도 시간이 촉박한 편에 속합니다.

pepper_mis   7달 전

제가 다른분 코드 참고해서 아래 코드 사용해서 통과되었는데, 이거랑 시간복잡도가 다른건가요?

djm03178   7달 전

코드를 부분만 올리시면 어떤 식으로 구현되어 있는 것인지 알기가 어렵습니다. 제출하신 코드를 확인해보니 방문 순서 자체가 cost의 오름차순이기 때문에 큐를 쓰지 않고도 진행할 수 있고 중복 방문도 일어나지 않습니다. 코드를 다시 보니 지금 코드로도 중복 방문에 대한 처리만 진행하면 같은 시간 복잡도로 통과 가능할 것 같습니다.

pepper_mis   7달 전

아하.. 중복 방문처리 차이였나보네요.. 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.