최단경로

[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 )

우선 이 문제를 풀기위해서는 벨만-포드 알고리즘을 이해해야한다. 벨만-포드 단일시작점 알고리즘 (출발 노드가 고정) 최단 경로 알고리즘 음수 간선 가능 음수 사이클 확인 가능 쓱 보면 다익스트라와 비슷해보인다.(https://guccin.tistory.com/112?category=977502) 그러나 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선에 대해서 최단거리를 알아낼수 있다. 또한 다익스트라는 우선순위 큐를 활용하여 최단 경로를 구하는데에 반해 벨만-포드는 매번 모든 간선을 전부 확인하며 최단거리를 알아내기 때문에 다익스트라보다 시간복잡도가 크다. 다익스트라 O(|E||log|V|), 벨만-포드 O(|E||V|) [c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 ) ..

[c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 )

다익스트라 다익스트라는 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 단일 시작점 알고리즘에 속하여 시작점을 기준으로 각 노드까지의 최단 거리를 알 수 있다. 이때 시간 복잡도를 줄이기 위해 우선순위 큐를 활용하면 좋다. 음수 간선이 없을때 사용 (음수가 있으면 벨만-포드나 플로이드를 사용하는게 좋다) 우선순위 큐를 활용 단일 시작점 알고리즘 다익스트라 알고리즘은 BFS처럼 동작한다. 시작점에서부터 BFS탐색을 진행한다. 단, 우선순위 큐에서 노드를 뽑을때는 간선의 가중치가 가장 낮은 노드를 뽑는다.(우선순위 큐에 {-가중치,노드} 형태로 넣으면 된다.) 해당 노드와 접한 노드를 뽑아서 dp에 최단경로를 메모이제이션한다. 이후 최단경로 가중치를 노드와 함께 큐에 넣고 루프를 돌며 반복한다. 문..

백준 2178 미로 탐색 (BFS, 최단 경로 탐색, 행렬그래프)

이번 문제는 BFS를 어떻게 최단경로로 활용할건지 이해해야한다. 처음에는 나도 BFS로 어떻게 최단경로를 구한다는 소리인지 알 수 없었다. 나도 완벽하게 이해하고 풀지 않았기 때문에 생각의 흐름을 나열해 볼까 한다. 우선 행렬그래프를 BFS의 트리 형태로 나열한다고 가정한다면 다음과 같은 그래프를 만들 수 있다. 그렇다면 우리는 (4,4)가 되기 위해서 7층까지 내려가야한다는 것을 단숨에 확인 가능하다. 그렇다면 BFS로 탐색을 하면서 언제가 몇층인지를 알아야한다. 따라서 층을 함께 표기해본다. 그러면 (1,1)이 1층인것을 알기 때문에 층에 큐에 넣은 인접 행렬에 대해서 2층이라는 것을 표기하여 큐에 삽입할 수 있다. 이러한 방식으로 (4,4)까지 진행하면 간단히 (4,4)가 7층에 있는 것을 알 수 ..