반응형 다익스트라5 백준 25430번 다이제스타 - C++ 풀이 1. 다익스트라를 사용하여 최단거리를 구한다. 2. 다익스트라 과정에서 마지막으로 이용한 간선의 가중치 w를 저장해 두고 더 큰 가중치의 간선만 사용하도록 한다. 3. 같은 노드에 도착하더라도 w에 따라 이용할 수 있는 다음 간선이 달라지므로 dist 배열은 dist[node][w]의 형태로 운영한다. 1. 다익스트라를 사용하여 최단거리를 구한다. 다익스트라 알고리즘을 사용하여 두 노드 사이의 최단거리를 구할 수 있다. 2. 다익스트라 과정에서 마지막으로 이용한 간선의 가중치 w를 저장해두고 더 큰 가중치의 간선만 사용하도록 한다. 단, 문제에서 주어진 조건에 따라 경로 내 간선의 가중치는 오름차순이 되어야 한다. 따라서 다익스트라 과정에서 이 조건을 만족할 수 있도록 마지막으로 이용한 간선의 가중치 w.. 2022. 8. 18. 백준 2307번 도로검문 - C++ 풀이 1. 다익스트라 알고리즘을 사용해서 최단 시간과 최단 경로를 구한다. 2. 최단 경로에 속한 간선들만 하나씩 지워보면서 최대 지연 시간을 찾는다. 1. 다익스트라 알고리즘을 사용해서 최단 시간과 최단 경로를 구한다. 먼저 검문을 하지 않았을 때 최단 시간을 알아야 지연 시간을 계산할 수 있다. 다익스트라 알고리즘을 사용해서 최단 시간을 구한다. 이때 최단 경로도 함께 구해둔다. 최단 경로에 포함되지 않은 도로를 검문해봤자 용의자가 최단 경로로 이동하면 지연시간이 0이기 때문에, 지연 시간을 최대로 하기 위해서는 최단 경로에 포함된 도로에서 검문을 해야 하기 때문이다. 2. 최단 경로에 속한 간선들만 하나씩 지워보면서 최대 지연 시간을 찾는다. 간선을 하나 지웠을 때 용의자의 최단 이동 시간도 다익스트라를.. 2022. 8. 10. 백준 16118번 달빛 여우 - C++ 풀이 1. 다익스트라를 이용하여 1번 정점에서 각 정점까지의 거리를 구한다. 2. 늑대의 경우 다익스트라 과정에서 홀수번째로 방문과 짝수번째 방문을 구분해서 기록한다. 1. 다익스트라를 이용하여 1번 정점에서 각 정점까지의 거리를 구한다. 한 정점에서 다른 모든 정점까지의 거리는 다익스트라 알고리즘을 사용하여 구할 수 있다. 2. 늑대의 경우 다익스트라 과정에서 홀수번째로 방문과 짝수번째 방문을 구분해서 기록한다. 늑대의 경우 한 간선을 홀수번째로 이용할 때와 짝수번째로 이용할 때 적용되는 가중치가 다르다. 따라서 한 정점을 홀수번째로 방문할 때와 짝수번째로 방문할 때 거리가 다르므로, dist 배열을 홀수, 짝수 각각 따로 기록해준다. i번 정점까지의 최종거리는 min(i번 정점을 홀수번째로 방문할 때의 거.. 2022. 7. 29. 백준 1162번 도로포장 - C++ 풀이 1. 다익스트라를 이용하여 1번 정점부터 N번 정점까지의 최소 거리를 구한다. 2. 다익스트라의 dist 배열을 포장 횟수까지 포함하여 운영한다. 3. 다익스트라 과정에서 간선을 포장하지 않는 경우와 포장하는 경우를 모두 고려한다. 1. 다익스트라를 이용하여 1번 정점부터 N번 정점까지의 최소 거리를 구한다. 두 정점의 최소 거리를 구하기 위해 다익스트라 알고리즘을 사용할 것이다. 2. 다익스트라의 dist 배열을 포장 횟수까지 포함하여 운영한다. 중간에 최대 K개의 간선의 가중치를 0으로 만들 수 있으므로, dist 배열을 포장 횟수까지 고려하여 2차원으로 운영한다. dist[idx][k] = 포장을 k번해서 1번 정점에서 idx번 정점으로 가는 최소 시간으로 정의할 수 있다. 3. 다익스트라 과정에서.. 2022. 7. 1. 백준 2211번 네트워크 복구 - C++ 풀이 1. 다익스트라 알고리즘을 사용해서 1번 정점에서 각 정점으로의 최단 거리를 구한다. 2. 1번 과정에서 각 정점을 최단거리로 방문하기 위해 직전에 방문한 정점을 기록해둔다. 3. 2번 과정에서의 기록을 가지고 최단거리로 전송하기 위해 필요한 간선들만 골라낸다. 1. 다익스트라 알고리즘을 사용해서 1번 정점에서 각 정점으로의 최단 거리를 구한다. 1번 슈퍼컴퓨터에서 각 컴퓨터로 최소 시간으로 패킷을 전송해야 한다. 따라서 1번 컴퓨터에서 각 컴퓨터까지의 최단 거리를 구해야 한다. 한 정점에서 다른 모든 정점으로의 최단거리는 다익스트라 알고리즘을 사용해서 구할 수 있다. 2. 1번 과정에서 각 정점을 최단거리로 방문하기 위해 직전에 방문한 정점을 기록해둔다. 구해야 하는 것은 최단 시간(거리)이 아니라 최.. 2022. 6. 4. 이전 1 다음 반응형
