안녕

0. 문제 링크 https://www.acmicpc.net/problem/1045 1045번: 도로 0부터 N-1까지의 번호가 매겨져 있는 N개의 도시와 두 도시를 연결하는 도로가 있다. 도로에는 우선순위가 있는데, A와 B가 (A < B) 도로 x로 연결되어 있고, C와 D가 (C < D) 도로 y로 연결되어 있을 때, www.acmicpc.net 1. 풀이 방법 edge가 (a, b)가 있다면, a < b가 되도록 모든 간선을 우선순위 큐에 넣음 이때 모든 간선의 개수가 m보다 작다면 -1을 출력 크루스칼 알고리즘을 사용하여 mst를 만들었음 만약 mst가 만들어지지 않으면, 모두 연결되지 않는 것이므로 -1을 출력 크루스칼 알고리즘을 진행하는 도중에 쓸모없는 간선은 따로 관리함 이때 우선순위 큐로 ..

0. 문제 링크 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 1. 풀이 방법 일단 문제를 보고 나서 MST를 구하는 문제라는 것은 쉽게 알아차렸음. 아무 생각 없이 크루스칼 알고리즘을 짜고 예제를 돌리는데, 틀렸음 왜 틀렸는지 곰곰히 생각을 해봤음 생각해 보니까 이게 무방향 그래프인데, 두 개의 노드에 최대 두 개의 무방향 엣지가 연결되는 것이 가능함 그래서 무방향 엣지 중에 작은 애를 고르고, 걔를 우선순위 큐에 넣었음 그러고 나서 ..

0. 문제 링크 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 1. 풀이 방법 전형적인 MST 문제 프림과 크루스칼 중 뭐로 풀까 고민했다. 시작은 프림으로 했는데, 이유는 시작 도시가 1번 도시이므로 1번부터 정점에 넣어서 MST를 탐색하는게 맞다고 생각했다. 근데 내 구현 issue로 인해, 엄청난 시간초과가 나버렸다... 그래서 결국 크루스칼 알고리즘으로 문제를 풀었다. 생각해보니까 어차피 MST면 1번 정점을 포함하니까,,,,뭐 그냥 크루..