본문 바로가기

알고리즘26

Dijkstra 알고리즘 다익스트라 알고리즘 또한 최단 경로를 구하는 알고리즘이다. 다익스트라는 최단 경로를 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로로 정의했다. 즉, 크루스칼이나 프림은 모든 정점을 잇는 간선들의 최소 비용을 도출했다면, 다익스트라 알고리즘은 특정한 시작 정점과 특정한 끝 정점까지의 최단 경로를 도출할 수 있는 것이다. 다익스트라와 비슷하게 하나의 시작 정점에서 끝 정점까지의 최단 경로를 구하는 알고리즘이 또 하나 있다. 바로 벨만-포드(Bellman-Ford) 알고리즘이다. 벨만 포드알고리즘은 음의 가중치를 허용하지 않는 다익스트라 알고리즘과 반대로, 음의 가중치를 허용한 상태에서 시작 정점과 끝 정점까지의 최단 경로를 계산한다. 이런 특성의 차이를 염두에.. 2023. 3. 30.
Prim 알고리즘 프림 알고리즘은 크루스칼 알고리즘과 비슷하게 MST를 만들어가는 방식 중 하나이다. 하지만 크루스칼 알고리즘과는 약간의 차이가 있다. 프림 알고리즘은 하나의 정점에서 연결된 간선들 중에 하나씩 선택하며 MST를 만들어 가는 방식인데, 우선 제일 먼저 임의의 정점을 하나 선택해서 시작하게 된다. 그 후 선택한 정점과 인접하는 정점들 중에서 최소의 비용을 가지는 간선이 존재하는 정점을 선택한다. 그 이후 위 두 줄의 방법을 모든 정점이 선택할 때 까지 반복한다. 크루스칼 알고리즘과 프림 알고리즘의 차이점은 간선을 선택하느냐 정점을 선택하느냐의 차이이다. 크루스칼은 간선의 가중치를 오름차순으로 정렬하여 간선의 가중치에 따라 선택하고, 프림은 정점을 선택해서 그 정점과 다른 정점 사이에 최소 비용을 가지는 간선.. 2023. 3. 30.
백준 1922번 네트워크 연결 G4 문제는 위와 같다. 놀랍게도 입력만 고쳐주면 최소 스패닝 트리 문제의 코드와 똑같이 내도 통과 가능하다. 같은 논리이기 때문이다. 구체적인 풀이는 최소 스패닝 트리 글을 확인하도록 하고, 전체 코드만 확인해보겠다. 전체 코드는 다음과 같다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Mai.. 2023. 3. 29.
백준 1197번 최소 스패닝 트리 G4 해당 문제의 조건은 위와 같다. 나는 이 문제를 크루스칼 알고리즘을 통해 풀었다. 우선 정점의 개수와 간선의 개수를 입력 받고, 간선의 개수만큼 배열을 만든다. 이때 배열은 2차원 배열로 A 정점, B 정점, 가중치를 입력받게끔 edges[i][3] 으로 만든다. StringTokrenizer st = new StringTokenizer(br.readLine()); int v = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken()); int [][] edges = new int [e][3]; 이런 식으로 만든 다음 차례대로 입력을 받는다. for(int i=0;i 2023. 3. 29.

티스토리툴바