다익스트라 (4) 썸네일형 리스트형 백준 16681 - 등산 https://www.acmicpc.net/problem/16681 힌트 더보기 집 -> 어떤 지점 방향으로는 올라가고 어떤 지점 -> 고려대학교 방향으로는 내려간다... 여기서 어떤 아이디어를 떠올릴 수 있겠는가? 풀이 더보기 어떤 지점 $X$를 기준으로 내려가야 되는 경로와 올라가는 경로가 다르다. 이를 살펴보면 $X$에서 고려대학교까지 내려가는 것은 고려대학교에서 $X$까지 올라가는 것과 같다. 따라서 다음과 같은 아이디어를 생각할 수 있다. 1. 집에서 올라가는 최단 경로 $sp_{1, x}$들을 계산한다. 2. 고려대학교에서 올라가는 최단 경로 $sp_{2, x}$들을 계산한다. 3. 어떤 지점 i에서 $sp_{1, i}$ 와 $sp_{2, i}$가 존재하면 i를 기준으로 문제 조건에 맞는 등산.. 백준 11779 - 최소비용 구하기 2 http://icpc.me/11779 출발 도시에서 도착 도시까지 최소비용을 구하는 문제이며, 이는 다익스트라 알고리즘을 그대로 적용할 수 있다. 하지만 최소비용뿐만 아니라 최소비용이 되기 위한 경로도 출력할 것을 요구하고 있다. 알아야 할 것 최단 경로의 해는 다익스트라 알고리즘을 수행하면서 배열로 저장할 수 있다. 우선순위 큐에서 꺼낸 노드 A와 A가 연결된 노드 B가 최적해를 갱신할 때 그 노드를 배열에 저장해주면 된다. 이렇게 하면 실제 최단 경로의 역순으로 노드가 구성된다. 구현 최단 경로를 저장하면서 다익스트라 알고리즘을 수행한 후, 저장된 최적해를 거꾸로 출력해주면 AC를 받을 수 있다. 전체 코드 더보기 #include using namespace std; using ll = long lo.. [ICPC] 백준 5719 - 거의 최단 경로 http://icpc.me/5719 Step 1. 최단 경로를 구해보자. 다익스트라를 통해 어렵지 않게 구할 수 있다. 만약 경로를 못찾으면 거의 최단 경로라는 말 자체에 모순이 있는 것이므로 -1를 출력해주자. 노드 간 간선이 최대 하나 존재할 수 있다는 설명과 후술할 step 2를 고려하여 인접행렬로 그래프를 구성하여 구성하자. 다익스트라를 통해 구한 시작점부터 각 정점까지의 길이는 따로 저장할 수 있도록 하자. Step 2. 도착점부터 시작점까지 bfs를 통해 거슬러 올라가도록 한다. 올라가는 과정에서 도착점까지의 길이 = 정점 i까지의 길이 + 정점 i와 도착점에 연결된 간선의 길이 를 만족한다면 그 간선은 최단 경로에 포함되는 간선이 된다. 해당 간선으로는 통행할 수 없도록 하자. 또한 최단 경.. 백준 10217 - KCM Travel https://www.acmicpc.net/problem/10217 시간제한이 10초라는 점과 어떤 도시로 가는 최소 시간을 구해야 하는 최단경로에 'M원 이하를 사용해야 한다'라는 제약 조건이 붙어있다. 인천에서 LA로 가는 최단 경로만 구해야 되므로 여기에 가장 특화된 다익스트라 알고리즘 사용을 최우선적으로 고려할 수 있다. 다만, 'M원 이하 사용'의 제약 조건으로 인해 DP가 가미된다는 걸 알 수 있는데 문제는 어떤 것을 메모이제이션 해야 하는가이다. DP 배열의 구성을 생각하기 위해 주어진 정보를 정리하면 출발하는 인천의 번호는 무조건 1이다. LA의 번호는 무조건 N(도시의 개수)이다. 시작과 도착이 고정되어 있으므로 다음 1차원 배열을 생각해볼 수 있다. DP[x] == 1에서 x까지의 최단.. 이전 1 다음
