Dijkstra12 백준 23801 자바 - 두 단계 최단 경로 2 (BOJ 23801 JAVA) 문제 : boj23801 한 점에서 모든 점으로의 최단거리를 알 수 있는 알고리즘 중에 다익스트라 알고리즘이 있다. 이 문제의 경우, x에서 p개의 점 중 적어도 하나를 방문한 후 z까지 가야 한다. 그럼 다익스트라로 x부터 다른 모든 점으로의 거리를 찾아도 답을 구할 수 없다. 이 문제의 경우 z점으로 들어가는 모든 지점의 거리도 알 수 있어야 한다. 이것도 다익스트라를 응용해서 할 수 있는데, 무방향 그래프라면 z에서 시작하는 다익스트라를 돌려도 그 결과가 모든 점에서부터 z로 향하는 최단거리와 동일하다. (참고로 방향이 있는 그래프일 경우에도 다익스트라로 모든 점에서부터 한 점으로의 최단거리를 구할 수 있는데, 모든 간선의 방향을 역방향으로 바꾼 후 다익스트라를 돌리면 된다.) 1. X에서 모든 점.. 2021. 12. 6. 백준 10282 자바 - 해킹 (BOJ 10282 JAVA) 문제 : https://www.acmicpc.net/problem/10282 가중치가 있는 방향 그래프에서 한점에서 시작해, 다른 모든 정점으로의 최단거리를 찾는 문제이다. 출력해야 하는 '총 감염되는 컴퓨터 수'는 최단거리가 무한대가 아닌 경우 즉 도달할 수 있다면 감염되는 컴퓨터이다. '마지막 컴퓨터가 감염되기까지 걸리는 시간'은 모든 정점으로의 최단거리 중 최대치를 출력하면 된다. 가중치가 있으므로 일단 BFS는 사용할 수 없고, DFS로는 시간초과를 피할 수 없다. Floyd-Warshall로는 O(100*10000^3) 이므로 역시 시간내에 통과할 수 없다. 쉽게 생각할 수 있는 이 문제에 딱 맞는 알고리즘은 다익스트라(dijkstra)이다. 시간복잡도는 대략 O(ElogV) 정도로 잡는다. -.. 2021. 11. 16. 이전 1 2 다음
