푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 단순한 다익스트라 알고리즘 구현 문제입니다 풀이는 아래 코드 참조 ✏️ 문제 코드 #include #include #include #include using namespace std; typedef paircur; vectortree; vectorvisit; vectordist; int main() { ios::sync_with_stdio(fa..

✏️ 문제 링크 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 다익스트라 알고리즘을 적용시켜서 풀었습니다. 다만 두 정점을 거쳐가야 하는 최단경로를 출력해야 하므로 다음과 같은 경우의 수로 나뉘었습니다. 두 정점을 A,B라 하고 시작점을1, 도착점을 N이라고 하면 ● 1 -> A -> B -> N ● 1 -> B -> A -> N ● 1 -> B -> A -> B -..

Algorithm 공부 #16 - 다익스트라 알고리즘  ✏️ 다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 그래프 상에서 한 정점에서 다른 정점들간의 최단 거리를 구할 수 있는 알고리즘이다.즉 도착 정점 뿐만 아니라 모든 다른 정점가지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾을 수 있다.매번 최단 경로의 정점을 선택해 탐색을 반복한다고 생각하면 될 것 같다.시간복잡도는 O(ElogV)이며 이때 특징으로는 에지값이 모두 양수여야 한다.최단 거리 알고리즘은 이외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있는데 이 알고리즘들은후에 포스팅을 할 예정이다.  ✏️ 구현 방법출발 노드와 도착 노드를 설정'최단 거리 테이블'을 초기화(출발 지점을 0으로, 나머지는..

백준 1916번 최단경로https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그www.acmicpc.net 정답 코드#include using namespace std; int INF = 987654321; int arr[1001][1001]; bool v[1001]; int d[1001]; int n, m, a, b, c, s, e; int getSmallIndex() { int min = INF; int index = 1; for (int i =..