Doby's Lab

https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 입력받으면서 모든 가중치를 더하고, MST를 구성하는 가중치 값들을 빼준다. 단, MST 간선의 개수 조건에 의해 간선의 개수가 N - 1이 되지 않았다면 -1을 출력한다. [AC 코드] #include #include #include #include #define MAX (..

https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net MST의 조건인 간선의 개수가 N - 1이 되지 않는다면 0을 출력해주면 된다. 가중치가 작은 간선부터 제외시키는 방법은 for의 범위를 조금씩 높이면 된다. [AC 코드] #include #include #include #include #define MAX (100000 + 1) #define pii pair #define ll l..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 그래프에서 전체적인 관점에서 보았을 때, 가중치의 합들이 최소가 되게 하는 문제다. >> MST 사용 >> 크루스칼 [AC 코드] #include #include #include #include #define MAX (100000 + 1) #define pii pair #define ll long long using namespace std; vector edges; int parent[MAX]; int n, m; bool cmp(pair a, pair b) { return a.seco..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 최소 스패닝 트리를 2개 가져야 하는데라고 생각하면 머릿속에 생각되는 트리 2개의 그림 때문에 접근이 어려웠다. 하지만, 문제에서 이 조건을 잘 봐야 한다. "마을에는 집이 하나 이상 있어야 한다." 이 말은 마을에 집이 하나만 있으면 된다고 말하는 것과 같다. 즉, 최소 스패닝 트리를 구하되 마지막 노드를 포함시키지 않는다면 두 마을이 형성될뿐더러 남아있는 ..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 공부한 블로그 (https://ansohxxn.github.io/algorithm/mst/) (https://yabmoons.tistory.com/186) [개요] 최소 스패닝 트리란? 방향이 없다. (양방향) 사이클이 없다. >> 트리라고 부르는 이유 모든 노드가 연결되어 있다. (간선이 없는 노드가 존재하면 안 된다.) 트리의 모든 가중치의 합이 ..

https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 저번에 풀었던 이 문제와 솔루션의 측면에서 비슷하다고 느꼈다.(https://draw-code-boy.tistory.com/191) 1) 모든 정점간의 최단 거리를 구한다. 2) 어떠한 거리를 구하는지 식을 완성하여 도출해낸다. [솔루션] 1) 데이터를 입력받고, 플로이드 와샬을 돌린다. 2) 두 정점을 선택하므로 완전 탐색(브루트 포스)으로 정점 두 개를 택하는 경..

https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 b.second; } }; vector dijkstra(int node) { priority_queue pq; vector dist(20 + 1, INF); dist[node] = 0; pq.push({ node, 0 }); while (!pq.empty()) { int now = pq.top().first; int cost = pq.top().second; pq.pop(); for (int i = 0; i < graph[now].size(); i++) { int next = graph[now][i].first; int nextCost = graph[no..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2차원 배열을 이용한 다익스트라 문제였다. 입력은 문자열을 처리해줘야 했으며 다음 노드로 가는 비용을 계산할 때 입력받은 2차원 배열을 이용하는 것을 까먹지 않으면 쉽게 풀리는 문제다. [AC 코드] #include #include #include #include #define MAX (100 + 1) #define pii pair #define INF 987654321 us..