Problem solving70 [BOJ] 1197. 최소 스패닝 트리 (C++) 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 찾고 가중치를 출력하기 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리 생각할 것 최소 스패닝 트리 문제이므로 크루스칼이나 프림 알고리즘 이용하기 코드 크루스칼 알고리즘 #include #include #include using namespace std; struct Edge { int start, end, cost; }; struct cmp { bool operator()(Edge &e1, Edge &e2) { return e1.cost > e2.cost; // 오름차순 } }; int find(int a, vector &parent) { if (parent[a] == a) return a; retur.. 2023. 7. 22. 최소 스패닝 트리 알고리즘 (크루스칼, 프림) 최소 스패닝 트리(Minimum Spanning Tree, MST) 그래프의 모든 정점을 사이클이 존재하지 않도록 연결했을 때, 간선의 가중치의 합이 최소인 트리 특징 무방향 그래프 하나의 그래프에서 최소 스패닝 트리는 여러개일 수 있다. 간선의 개수는 N-1개이다 크루스칼(Kruskal) 알고리즘 가중치가 낮은 간선일수록 최소 스패닝 트리에 포함될 가능성이 클 것이다. 이런 점을 이용하여 그래프의 모든 간선을 오름차순으로 정렬 후 사이클이 생기지 않도록 트리에 하나씩 추가해보는 알고리즘이다. 사이클을 확인할 때는 유니온 파인드를 이용한다. 알고리즘 구조 // 1. 모든 간선을 우선순위 큐에 넣어 오름차순으로 정렬 sturct cmp { bool operater()(Edge& e1, Edge& e2) {.. 2023. 7. 21. [BOJ] 11870. 플로이드2 (C++) 문제 n개의 도시가 있다. 한 도시에서 출발해 다른 도시에 도착하는 m개의 버스가 있다. 모든 도시의 쌍에 대해 최소 비용을 출력하고 갈 수 없는 경우에는 0을 출력 그 다음, 도시 간의 최소 비용에 포함되어 있는 도시의 개수와 경로를 출력, 갈 수 없는 경우에는 0 출력 생각할 것 모든 도시에서 모든 도시로 가는 최소 비용을 구해야하므로 플로이드 워셜 알고리즘을 사용하기 중간에 경로는 어떻게 구할까? vector route; void find_route(int i, int j, vector via) { if (via[i][j] == 0) { route.push_back(i); route.push_back(j); return; } find_route(i, via[i][j], via); route.pop_.. 2023. 7. 21. [BOJ] 11657. 타임머신 (C++) 문제 N개의 도시가 있다. 한 도시에 출발해서 다른 도시에 도착하는 버스가 M가 있다. 이때 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다. 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력 해당 도시로 가는 경로가 없다면 -1 출력 만약 1번 도시에서 출발해 어떤 도시로 가는 시간을 무한히 오래 전으로 되돌릴 수 있으면 첫 줄에 -1 출력 생각할 것 문제에서 시간 C가 양수가 아닌 경우가 있고, 특정 도시에서 출발하므로 벨만 포드 알고리즘을 사용하자 시간을 무한히 오래 전으로 되돌릴 수 있다 → 음수 사이클의 경우 판별하자 제출 중에 계속 출력 초과가 떴.. 2023. 7. 21. 이전 1 ··· 7 8 9 10 11 12 13 ··· 18 다음