deulee의 개발 노트

문제 방향성이 없는 간선이 주어지고 정점 1부터 정점 N까지 도착하는 최단 경로를 구하는 것이다. 이때 정점 X, Y를 경유하는 최단 경로를 구해야 하는 문제이다. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 nDis) { disArr[flag][nNode] = nDis; pqarr.push(std::make_pair(nNode, nDis)); } } } } void init(void) { for (int i = 0; i > N >> M; for (int i = 0; i < M;..

알고리즘/문제 2023. 5. 21. 20:36

BFS는 가중치가 있는 간선이 있는 그래프에서는 최단 거리 알고리즘으로써 사용될 수 없다. 그 이유는 BFS는 방문한 순서대로 동작을 하게 되기 때문이다. 그렇기 때문에 다음과 같은 상황에서 전혀 사용할 수 없는 것이다. 시작점이 A라고 가정해보자. 시작점 A를 방문하게 되었을 때 BFS 알고리즘을 이용하게 된다면 (2, B)와 (12, C)를 '그냥 큐'에 넣게 될 것이다. 그리고 나서 D를 방문하게 되고 알고리즘은 종료를 하게 될 것이다. 이렇게 될 경우 BFS 알고리즘 입장에서 A에서 C까지의 최단 경로가 12가 되는 것이다. 실제로는 2 + 4 + 3 = 9 인데도 말이다. 즉, A에서 C까지의 최단 경로는 A to C가 아니라 A to B to D to C가 되는 것이다. 이러한 상황에서 BFS..

알고리즘/이론 2023. 5. 21. 20:20

다익스트라(Dijkstra) 알고리즘은 그래프 이론을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘이다. 이 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 하지만 이 때 음의 간선을 포함하고 있는 경우 이 알고리즘은 사용할 수 없다는 점을 기억하고 이 글을 읽어보도록 하자. 하지만 애초에 다익스트라(Dijkstra) 알고리즘 BFS(너비 우선 탐색)을 기반으로 만들어진 알고리즘이기 때문에 BFS와 유사한 점이 많이 있다. 하지만 BFS는 가중치가 있는 그래프, 즉 각 간선마다 비용이 정해져 있는 경우 사용할 수 없다. 그 이유는 너비 우선 탐색은 발견한 순서부터 탐색을 시작하기 때문이다. 이 이유는 다른 장에서 따로 설명하도록 하겠..

알고리즘/이론 2023. 5. 21. 20:12