백준 17741 1774. 우주신과의 교감 (Python) 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 최소 신장 트리(MST)를 이용하여 해결하는 문제이다. MST를 만드는 방법에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 자세한건 검색을 통해 알아보자. 간단하게 설명하면 다음과 같다. * 크루스칼 알고리즘 : 모든 간선을 길이에 따라 오름차순으로 정렬하여 크기가 작은 간선부터 사용한다. 간선을 사용했을 때 사이클이 발생하지 않는지를 체크한다. * 프림 알고리즘 : 시작 정점을 기준으로 선택할 수 있는 간선 중 가장 크기가 작은.. 2022. 6. 10. 이전 1 다음
