https://www.acmicpc.net/problem/11657알고리즘 분류 : 그래프 이론, 최단 경로, 벨만–포드❓문제 🔅해석 1. 거리 초기화 시작 정점의 거리를 0으로 설정하고, 나머지 모든 정점의 거리를 무한대로 설정한다. 2. 거리 갱신 모든 간선에 대해 V-1번 반복해서 간선의 시작 정점에서 도착 정점으로 가는 경로가 현재 알려진 경로보다 짧다면, 그 경로를 갱신한다.dist[from] > dist[to] + edge.cost 이므로 dist 업데이트를 한다. dist[from] > dist[to] + edge.cost 이므로 dist 업데이트를 한다. dist[from] == dist[to] + edge.cost 이므로 dist 업데이트 되지 않는다. dist[from] 이렇게 (..
https://www.acmicpc.net/problem/1753알고리즘 분류 : 그래프 이론, 데이크스트라, 최단 경로❓문제🔅해석음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제에서는 다익스트라 알고리즘이 사용된다.다익스트라 알고리즘은 인접리스트 형태로 그래프를 저장하고, Priority Queue를 사용하여 최소 비용의 정점이 먼저 나오도록 한다. // input5 615 1 11 2 21 3 32 3 42 4 53 4 6 1. 인접 리스트 생성ArrayList[] adjList = new ArrayList[V + 1]; 2. start로 부터 각 노드까지 최단거리를 담는 dist 배열과 노드를 방문했음을 체크하는 visited 배열을 생성한다. 3. Priority ..
MST (최소 신장 트리)Minimum Spanning Tree가중치가 있는 연결 그래프에서 모든 정점을 포함하면서, 간선의 가중치 합이 최소가 되는 트리이를 찾기 위한 대표적인 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘(Kruskal's Algorithm)그래프의 모든 간선을 가중치 순으로 정렬한 후, 가중치가 가장 작은 간선부터 선택하여 트리를 구성하는 방법이다.이 과정에서 사이클을 형성하는 간선은 선택하지 않는다.간선 위주, union-find 사용 순서간선 정렬: 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.간선 선택: 정렬된 간선 리스트에서 순차적으로 간선을 선택한다. 이때, 선택된 간선이 사이클을 형성하지 않는다면 해당 간선을 최소 신장 트리에 추가한다..
