문제 풀이/백준 (BOJ)

[백준/BOJ] 1854번: K번재 최단경로 찾기( 다익스트라 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1854 풀이이 문제는 1번 도시에서 다른 도시까지 갈 수 있는 경로에 걸리는 시간 중에서 k번째 시간을 출력하는 문제입니다. 여기서는 한 도시에서 다른 도시까지 가는 데 걸리는 시간이 양수이므로, 다익스트라( Dijkstra ) 알고리즘을 사용합니다.다익스트라 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘다익스트라( Dijkstra ) 알고리즘 소개다익스트라 알고리즘은 출발 노드로부터, 도달이 가능한 모든 노드까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.이 알고리즘은 그래프에 음수 가codingembers.tistory.com 그렇지만, 단..

2024. 8. 12.
알고리즘

[C++] 최단 거리를 구하는 플로이드-워셜 알고리즘

플로이드-워셜( Floyd-Warshall ) 알고리즘 소개플로이드-워셜 알고리즘은 주어진 그래프에서 모든 정점 간에 최단 거리를 구하는 알고리즘입니다.이 알고리즘은 정점 간의 거리가 음수로 주어져도 최단 거리를 구할 수 있습니다. 시간 복잡도정점의 개수가 V일 때,이 알고리즘은 시간 복잡도는 $O(V^3)$입니다. 이 알고리즘 구현이 알고리즘의 아이디어는 A -> C로 가는 최단 거리는 A->B로 가는 최단 거리와 B->C로 가는 최단 거리의 합으로 만들어진다는 것입니다. 예를 들면, 위 그래프의 A에서 C까지의 최단 거리는 A에서 B까지의 최단거리와 B에서 C까지의 최단거리의 합인, 1 + 5 = 6이 됩니다. 이 아이디어를 구현하기 위해 플로이드-워셜 알고리즘은 인접 배열을 통해 그래프를 표현합니다..

2024. 8. 12.
문제 풀이/백준 (BOJ)

[백준/BOJ] 11657번: 타임머신 ( 벨만-포트 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/11657 풀이이 문제는 1번 도시에서 출발하여, 다른 도시까지 이동하는 데 걸리는 가장 빠른 시간을 출력하는 문제입니다. 이러한 문제를 푸는데 적용할 알고리즘으로 다익스트라( Dijkstra )와 벨만-포드( Bellman-Ford ) 알고리즘이 있습니다.그런데, 주의할 점은, 이동하는 데 걸리는 시간이 음수인 경우가 있다는 것입니다. 다익스트라 알고리즘의 경우 음수 입력 데이터에 따라 문제를 해결하지 못할 수도 있습니다.따라서, 벨만-포드 알고리즘을 사용합니다. 벨만-포드 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 벨만-포드( Bellman-Ford ) 알고리즘벨만-포드( Bellma..

2024. 8. 10.
알고리즘

[C++] 최단 거리를 구하는 벨만-포드( Bellman-Ford ) 알고리즘

벨만-포드( Bellman-Ford ) 알고리즘의 소개벨만-포드 알고리즘은 출발 정점으로부터, 도달이 가능한 모든 정점까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.이 알고리즘의 장점은 음수의 가중치를 가진 순환 경로가 있는 경우, 그러한 순환 경로가 있다는 것을 판단할 수 있다는 것입니다. 같은 목표를 가진 다익스트라( Dijkstra ) 알고리즘은 이러한 경우, 잘못된 결과를 내고, 문제 해결에 실패합니다.다익스트라 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘다익스트라( Dijkstra ) 알고리즘 소개다익스트라 알고리즘은 출발 노드로부터, 도달이 가능한 모든 노드까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다...

2024. 8. 10.
문제 풀이/백준 (BOJ)

[백준/BOJ] 1753번: 최단 경로 ( 다익스트라 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1753 풀이이 문제는 출발 노드로부터 도달이 가능한 모든 노드들까지의 최단 거리를 구하는 문제입니다. 이 문제를 해결할 수 있는 알고리즘으로 다익스트라( Dijkstra )와 벨만-포드( Bellman-Ford) 알고리즘이 있습니다.그런데, 간선의 가중치가 양수인 경우, 다익스트라 알고리즘이 좀 더 빠릅니다. 다익스트라 알고리즘에 관한 내용은 여기에서 볼 수 있습니다. [C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘다익스트라( Dijkstra ) 알고리즘 소개다익스트라 알고리즘은 출발 노드로부터, 도달이 가능한 모든 노드까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.이 알고리즘은 그래프에 음수..

2024. 8. 10.
알고리즘

[C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘

다익스트라( Dijkstra ) 알고리즘 소개다익스트라 알고리즘은 출발 노드로부터, 도달이 가능한 모든 노드까지의 최단 거리들을 한 번에 계산하는 알고리즘입니다.이 알고리즘은 그래프에 음수 가중치의 순환 경로가 존재하는 경우, 최단 거리를 구하지 못하는 제약이 있습니다. 시간 복잡도V: 노드의 수, E: 간선의 수일 때,이 알고리즘의 시간 복잡도는 O( E logV )입니다. 알고리즘의 실행 과정이 알고리즘의 실행 과정은 다음과 같습니다. 1. 출발 노드의 최단 거리를 0으로 설정합니다.    그리고, 나머지 노드들은 최대 값( ∞ )의 최단 거리를 가진 것으로 설정합니다. 2. 현재, 최단 거리를 가진 노드를 선택합니다. 3. 선택된 노드에 연결된 모든 노드에 대해 다음의 비교를 수행해서 더 짧은 거리..

2024. 8. 10.