mst 썸네일형 리스트형 1197 최소 스패닝 트리 mst 기본 문제 요즘에 너무 복붙만 해서 블로그 못 보면 문제를 못 풀 것 같았다. 그래서 아예 초심으로 돌아가서 그냥 백지에다 정리한 다음 풀었다. 암튼 문제를 풀기 전 백지에 두어번 적어보면서 풀었다는 걸 강조한다. 풀이는 간단하다. - Edge 입력받기 - 가중치 기준으로 정렬한다 - 가중치가 작은 것부터 더해간다 시간 복잡도는? - 정렬이 nlogn (eloge) - edge 확인하면서 유니온파인드 find, merge -> 이것도 nlogn (elogv) - e가 10만 이하라 시간복잡도 터지지 않는다 #include #include #include #include #include #include #include #include #include #include #include #include .. 더보기 14621 나만 안되는 연애 그래프의 최단 거리를 구해야 하기 때문에 MST를 사용하면 되겠다 싶었다. 그런데 MST를 일년 전에 공부했고 자료도 정리해놓지 않아서.... 다시 이해하는데 오래 걸렸다. 그리디하게 가장 edge를 구해놓고 가장 짧은 것부터 뽑아서 계산한다. Union Find로 해당 간선이 이미 계산된 간선인지 확인한다. 코드는 1. 학교 입력 받으면서 유파 초기화 2. 여-남 경우에만 간선을 추가한다 3. 간선을 오름차순으로 정렬한다 -> 그리디하게 가장 짧은 것부터 뽑기 위해서 4. 가장 짧은 길이부터 뽑아서 더한다, 간선을 몇 개 더했는지도 계산한다 5. 간선이 n - 1개가 아닌 경우 노드를 전부 확인 안 했으니 -1을 출력한다 #include #include #include #include #include .. 더보기 이전 1 다음
