deulee의 개발 노트

문제 정점 N개와 M개의 간선이 주어진다. A번째 정점에서 B번째 정점까지 도달하는 데 드는 최소 비용을 출력하라. 입력 첫째 줄에 N(1 M; for (int i = 0; i > X >> Y >> C; varr[X].push_back(P(Y, C)); } for (int i = 0; i > S >> D; Dijkstra(S); std::cout

알고리즘/문제 2023. 5. 23. 15:19

문제 N개의 정점으로 이루어진 그래프 G가 있고, 그래프 G의 모든 간선은 가중치를 2개 가지고 있다. 이 말은 특정 노드 i에서 특정 노드 j로 가는 가중치가 2개 있다는 것이다. 0번 정점에서 1번 정점으로 가는 최단 경로를 찾아야 한다. 경로의 비용은 경로에 있는 간선의 가중치 1을 모두 더한 값인 W1와 가중치 2를 모두 더한 값인 W2를 곱해서 구할 수 있다. 여기서 곱하는 것에 유의하며 문제를 풀어야 한다. 입력 첫째 줄에 정점의 수 N이 주어진다. (2 b.idx) return true; else return false; } return false; } }; std::vector varr[2][21]; int dist[2][21]; int INF = 1e8; int Dijkstra(int S..

알고리즘/문제 2023. 5. 23. 11:13

문제 방향성이 없는 간선이 주어지고 정점 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

문제 N개의 정점이 있고 각 정점에서 특정 점정 X가 정해진다. 이때 각 정점에서 i를 방문하고 다시 자기 자신의 정점으로 돌아오는 최소 길이를 구한 뒤 가장 많은 비용을 소비하는 정점을 구하는 문제이다. 입력 첫째 줄에 N(1 tmpDis + nextDis && nextNode != Node) { disArr[flag][nextNode] = tmpDis + nextDis; pqarr.push(std::make_pair(nextNode, disArr[flag][nextNode])); } } } } void init(void) { for (int i = 0; i < 1001; i++) { disArr[0][i] = INF; disArr[1][i] = INF; } } int main(void) { int N..

알고리즘/문제 2023. 5. 21. 18:02