다익스트라7

• [다익스트라] 백준 1753 최단경로 이번 포스팅에서는 백준 1753번 문제를 다익스트라 알고리즘을 활용하여 풀이하는 방법을 다뤄보겠습니다. 이 문제는 특정 시작점에서 다른 모든 정점으로 가는 최단 경로를 찾는 문제로, 그래프 이론에서 자주 등장하는 문제 유형입니다.문제 설명주어진 그래프에서 시작점으로부터 다른 모든 정점으로의 최단 경로를 구하는 문제입니다. 그래프는 방향성이 있으며, 간선마다 가중치가 부여되어 있습니다. 다익스트라 알고리즘은 이와 같은 가중 그래프에서의 최단 경로 문제를 효율적으로 해결할 수 있는 알고리즘입니다.다익스트라 알고리즘 개요다익스트라 알고리즘은 그래프 이론에서 가장 널리 사용되는 최단 경로 탐색 알고리즘 중 하나입니다. 이 알고리즘은 가중치가 있는 그래프에서, 하나의 시작 정점으로부터 다른 모든 정점으로 가는 최.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 8. 10.

• [다익스트라]백준 20182 골목 대장 호석 - 효율성 1 package 다익스트라; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; public class boj_20182_골목대장호석효율성1 { private static int n, m, a, b, c, maxCost, cost[]; private static List[] v; static class Node implements Comparable{ int node; int cost; int shy; Node .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 2.

• 

  백준 11779 java - 최소비용 구하기 2 (다익스트라) 해당 문제는 다익스트라 알고리즘 문제이다. 최소비용 구하기 문제와 다른 점은 최소 비용 갖는 경로와 도시 갯수를 출력하는 것인데 이것은 따로 배열을 만들어서 출력하면 되는 부분이므로 크게 힘든 점은 없었다. 2022.07.15 - [알고리즘공부(AlgorithmStudy)/알고리즘이론(AlgorithmTheory)] - 백준 1916 java - 최소비용 구하기(다익스트라 알고리즘) 1. 다익스트라를 구현한다. 2. 우선순위 큐에 comparator를 넣는 버전이 아닌 Node 클래스 생성 및 compareTo 메소드 오버라이딩 하는 방식으로 구현 해봄 3. 이전 경로 등록할 배열 생성 4. 다익스트라 알고리즘 실행 후 최소 비용 갖는 경로 및 도시 갯수 구하기 5. 출력 백준 1916 java - 최소.. 카테고리 없음 2022. 7. 21.

• 

  백준 1916 java - 최소비용 구하기(다익스트라 알고리즘) 전형적인 다익스트라 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.sql.Array; import java.util.*; public class Boj_1916_최소비용구하기 { public static void main(String[] args) throws IOException { PriorityQueue pq = new PriorityQueue(new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o1[1] - o2[1]; } }); BufferedReader br .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 7. 15.

• 

  백준 1238 java - 파티(다익스트라) 해당 문제는 다익스트라 N번 또는 2번으로 풀 수 있는 문제이다. 1. N번 돌리는 경우에는 A -> X로 가는 경우 N-1번, X->A가는 경우 1번 해서 N번 돌리면 된다 2. 2번 돌리는 경우에는 X -> A로 가는 경우 1번과 간선을 반대 방향으로 저장한 간선리스트로 1번 다익스트라를 돌리면 된다. 3. 2번 다익스트라를 돌리는 경우가 가능한 이유는 X에서 다른 노드에 가는 경우는 이해가 되겠지만 간선리스트를 반대방향으로 저장한 경우 특정 노드에서 X로 가는 길이가 바로 A -> X로 가는 경우 N-1번과 동치이기 때문이다. package 다익스트라; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 7. 3.

• 

  백준 14938 java - 서강 그라운드(플루이드와샬, 다익스트라) 해당 문제는 35분여간 bfs로 풀다가 밑에 문제 분류 보고 플루이드와샬, 다익스트라인 걸 보고 바로 플루이드와샬로 돌려서 풀었다. 그 과정에서 문제를 입력값을 제대로 안봐서 m, r를 혼동하는 바람에 이왜틀 3분간 시전... 1. A에서 B까지 가는 거리가 m(수색가능 범위) 이내면 아이템 회수 가능 2. BFS돌리면서 계속 합해줘서 MAX값 찾아야 겠다. 3. 이왜틀???? 아! bfs로 방문처리하면 더 최단거리가 될 수 있음에도 불구하고 방문처리돼서 최단거리로 가는 게 아닐 수 있겠구나 4. 다익스트라 구현보다 플루이드와샬이 구현할 때 더 빠르니까 플와 써야겠다. 5. 문제 접근, 풀이, 제출, pass까지 약 50분 소요 import java.io.BufferedReader; import java.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 7. 2.

• 

  백준 1504 java - 특정한 최단 경로(최적화된 다익스트라) 해당 문제는 다익스트라를 이용한 문제로 다익스트라를 까먹고 다시 공부해서 풀게 된 문제이다. 1. 정점의 개수 N(2 ≤ N ≤ 800), 간선의 개수 E(0 ≤ E ≤ 200,000), 거리 c (1 ≤ c ≤ 1,000) 2. 다익스트라를 3번 돌리면 된다. (1에서 한 번, v1에서 한 번, v2에서 한 번) 3. 최적화된 다익스트라 기준 시간 복잡도 O(logN*(N+M)) = O((N+M)logN)(N은 정점 수 , M은 간선 수) -> 3번 돌리므로 3*O((N+M)logN) 4. distance의 INF값은 무지성 Integer.MAX_VALUE를 쓰기보다 정확한 계산을 근거로 넣어야 하므로 싸이클 다 돈다고 생각하면 800 x 1000 이므로 800,000보다 큰 값을 INF값으로 대체해서.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 4.