Competitive Programming 3rd(Uva Judge)8 다익스트라 알고리즘(Dijkstra), 가중치가 있는 그래프의 최단 경로 다익스트라(Dijkstra) 알고리즘 가중치가 없는 그래프인 경우 BFS를 수행하면 시작점으로 부터 각 정점 까지의 최단 거리를 구할 수 있다. 만약 그래프의 간선이 가중치를 갖는다면 BFS를 이용하여 최단거리를 구하는것은 불가능 하다. 간선의 가중치로 인해 시작점에서 도착점 까지 거치는 간선의 갯수가 해당 경로의 거리가 아니기 때문이다. 거치는 간선의 갯수와는 관계없이 간선의 가중치의 합이 최소가 되는 경로가 최단 경로가 된다. 이와 같은 문제를 해결하기 위한 알고리즘이 여러개 있지만 이 중 그래프에 음수 사이클이 없는 경우 단일 시작점 최단 경로를 구하는 대표적인 알고리즘이 다익스트라 알고리즘이다. 해당 그래프의 최단경로를 구하기 위하여 다익스트라 알고리즘을 구현 하고자 한다면 우선순위 큐와 시작점부.. 2018. 1. 27. 최소 스패닝 트리(MST, Minimum Spanning Tree) 최소 스패닝 트리(MST) 스패닝 트리란 그래프에 모든정점을 연결하는 트리이다. 스패닝 트리 중, 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 스패닝 트리가 최소 스패닝 트리가 된다. 정점의 갯수가 V개인 그래프의 최소 스패닝 트리는 V - 1개의 간선을 갖는다. 최소 스패닝 트리를 구하는 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 있다. 두 알고리즘에 대해서 설명할 것이다. 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 첫번째로 그래프의 간선 리스트를 구성한다. 간선 리스트를 간선의 가중치를 기준으로 오름 차순으로 정렬하고 가중치가 가장 작은 간선부터 스패닝 트리에 해당되는 간선에 추가한다. 이때 사이클이 발생하는 간선은 추가 하지 않고 무시한다. 사이클의 여부는 U.. 2018. 1. 26. Uva 11456 - Trainsorting Problem Link https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=651&problem=2451&mosmsg=Submission+received+with+ID+20661170 Description of Problem 자동차의 행렬이 주어진다. 행렬에는 자동차의 무게가 저장된어 있다. 이때 자동차를 연결한다. 자동차를 연결하는 제약조건은 앞쪽 즉, 왼쪽의 자동차가 뒷쪽 즉, 오른쪽의 자동차보다 무거워야 된다. 이때 주어진 조건을 만족하는 가장 긴 자동차 행렬의 길이를 구하는 문제다. Algorithm to Solve the Problem 답은 제약조건을 만족하는 가장 긴 행렬의.. 2018. 1. 25. 절단점 및 다리(구하기) 절단점 및 다리(Articulation Point & Bridge) 절단점은 그래프G의 정점 중에서 이를 제거했을때(이때 해당 정점에 인접한 간선들도 같이 제거한다) G가 연결되지 않도록 만드는 정점이다. 절단점이 한개도 없는 그래프를 이중 결합 되었다고 한다. 다리는 그래프 G의 간선 중에서 이를 제거했을때 G가 연결 되지 않게 만드는 간선이다. 이둘을 찾는 문제는 보통 무방향 그래프에 대해서 정의된다. Algorithms to get Articulation Point and Bridge 우선 가장 직관적이지만 약간 비효율적인 알고리즘을 소개 하겠다. 첫째. DFS를 수행하여 그래프 G가 몇개의 컴포넌트로 구성되었는지를 파악한다.둘째. 모든 정점을 한번씩 순회하며 해당정점과 정점에 인접한 간선을 제거한.. 2018. 1. 19. 이전 1 2 다음