목록알고리즘/최단 경로 (2)

김미썸코딩

이코테 최단경로 : 전보 [C++] - 다익스트라

알고리즘을 풀기 전, 최단 경로 알고리즘은 크게 두가지로 나뉜다는 것을 배웠다. 다익스트라 알고리즘은 그리디 알고리즘의 성격을 띠며 한지점에서 여러지점으로 가는 최단 경로를 구한다. 플루이드 워셜 알고리즘은 여러지점에서 여러지점으로 가는 최단 경로를 구한다. 따라서, 다익스트라는 배열에 노드별 결과값을 저장하며 플루이드 워셜은 이차원 배열에 결과값을 저장한다. 이번에 풀어본 "전보"라는 문제는 시작지점인 START에서 다른 노드들로 가는 최단 거리를 구한 다음, 도달할 수 있는 노드의 갯수와 구한 최단 거리들 중 가장 짧은 거리를 구하는 문제였다. 문제는 다음과 같다. 풀이는 다음과 같다. #include #include #include #include #include #define INF 1e9 usi..
알고리즘/최단 경로 2021. 5. 31. 15:47
백준 11403번 : 경로 찾기 [C++]

Floyd Warshall 알고리즘으로 푸는 문제였다. Floyd Warshall 알고리즘은 두 정점간의 거리의 최단거리를 구하는 알고리즘이다. 거쳐가는 정점을 기준으로 두 정점이 각각 연결되어있다면 두정점은 연결된 상태라고 보는 것이 바탕이다. i - k - j 일때, k를 기준으로 for문을 돌리면서 i - k - j 거리를 i - j 거리로 정의하는데 "min( i - j 거리 , i - k - j 거리 )" 를 반복한다. #include #include //#include //memset #include using namespace std; const int MAX = 100; typedef struct { int y, x; }dir; int N; int graph[MAX][MAX]; void f..
알고리즘/최단 경로 2020. 8. 9. 17:58
Prev 1 Next