Minimum Spanning Tree

[백준] 28297. 차량 모듈 제작 - C++

[UCPC 2023 예선 C번] [Gold I] https://www.acmicpc.net/problem/28297 28297번: 차량 모듈 제작 현대모비스는 한국 외에도 유럽, 중국, 미국, 인도 등 여러 곳에 연구소를 두고 자율주행, 전동화, 커넥티비티 등의 미래기술은 물론 기존 기계 부품(제동, 조향, 현가, 안전, 램프 등)에도 ICT 기 www.acmicpc.net 풀이 수학적 지식과, MST(Minimum Spanning Tree)를 이용해 풀 수 있었던 문제. 대회 당일에는, 시간을 얼마 안 남겨놓고 풀이를 시작해서, 조급하게 Union-Find로 접근하다 O(N^3)으로 TLE를 냈는데, 끝나고 다시 보니 MST로 풀이하면 된다는 것을 깨달았다...! 우선, 두 점 사이의 유클리드 거리는 ..

[백준] 1647. 도시 분할 계획 - python

[Gold IV] 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 풀이 문제를 딱 보고서 생각한 것 -> Minimum Spanning Tree구나. MST를 구현하고 나서, 남은 edge들 중 가장 value가 높은 것을 제거하면 될 것 같다. line 13의 = 를 ==로 오타내서 찾는데 시간 좀 씀...ㅎ 아무튼 clear. from collections import deque N, M = map(in..

[프로그래머스] 42861. 섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최소 신장 트리 (MST)의 Kruskal 알고리즘을 이용하여 풀었음. 우선 cost에 따라 오름차순으로 배열 정렬. vertex의 연결을 저장하고, Union-Find에 이용할 dicionary를 하나 생성하고, union-find를 구현(find, union func.) Kruskal 알고리즘을 적용해 cost가 낮은 순으로 정렬한 edge들에 대해 순회하며 사이클이 생기지 않도록 간선(..