다익스트라 검색 결과

해당 글 3건
정보를 잘 저장해서 사전순 다익스트라 문제를 풀어봅시다.

얼마전에 추가된 tony님 문제를 풀었습니다. 필수 유형들과 어려운 유형들이 몇 개 있는데요. 알아가면 좋을 법한 트릭을 하나씩 소개해 드리겠습니다. 먼저 산책 시리즈입니다. large나 small이나 별 다른 건 없으니, 풀어보도록 합시다. 문제를 읽어보면, 제일 중요한 것은 딱 하나임을 알 수 있어요. S에서 E로 갈 때 최단 거리가 여러개 있다면 사전 순으로 가장 앞선 것을 택해라. k번째는 훨씬 어려워서, 사전순으로 가장 앞선 것을 택하라고 했을 겁니다. 그러면 어떤 정보가 필요할까요? 즉, 모든 i에 대해서, e까지의 최단 거리를 구해야 함을 알 수 있어요. 이런 그래프가 있고, s가 1, e가 4라고 해 봅시다. 처음에 우리는 1에서 4까지 가는 최단 경로 중에 사전순으로 앞선 경로를 구해야 ..
자료알고/알고리즘 2021. 8. 11. 16:00
정점 분할 : 노드를 상태에 따라 여러 개로 쪼갠다.

5002번째로 푼 문제는 이 문제였습니다. 문제 상황을 간단하게 요약하면 아래와 같습니다. 1순위가 같으면 2순위를 처리하는 것은 나중에 생각해 보도록 합시다. 우리가 원하는 것은 '탑승 비용', 문제에서 설명하는 route cost를 최소화 하는 방법부터 고민해 보겠습니다. 비행기 1이 도시1에서 3을 거쳐서 목적지인 7로 간다고 해 봅시다. 대충 1에서 7로 가는데 3을 경유한다고 보시면 됩니다. 이 경로를 선택하는 비용이 10이라고 해 보겠습니다. 문제에서 설명하는 것에 따르면 1에서 3으로 가는 탑승 비용, 3에서 7로 가는 탑승 비용, 1에서 7로 가는 탑승 비용이 10으로 같습니다. 이 세 경우는 경로 1을 선택해서 갈 수 있는 경우이기 때문입니다. 문제는, 비용 10을 어느 간선에 줄 것이냐..
자료알고/알고리즘 2020. 12. 29. 04:01
다익스트라 알고리즘 : 이미 결정된 노드의 인접 노드를 또 탐색하면 어떻게 될까요?

이 글을 읽기 전에 잘못 구현된 다익스트라 글을 보고 오시는 것 추천드립니다. 저는 그 글을 읽으셨고, 그 글에 나온 저격 데이터가 어떠한 원리로 작성되었는지 30% 정도 이해했다는 전제 하에 진행하도록 하겠습니다. 보통 이 알고리즘을 구현하실 때 Priority Queue를 이용하는 경우가 많습니다. 저는 그것을 기준으로 작성하였습니다. min_cost와 where_is_from, visit와 con이 있습니다. 이 중에서 con은 graph를 구축하는데 쓰이는 자료구조 정도로 생각하시면 됩니다. C++의 STL에서 vector con과 같습니다. min_cost를 inf로 초기화 합니다. 그리고, where_is_from을 -1로, visit를 false로 초기화를 합니다. 다음에 pq에 시작점을 넣..
자료알고/알고리즘 2020. 8. 11. 23:50