최소 신장 트리 검색 결과
3 개의 검색 결과가 있습니다.
알고리즘 문제풀이[Algorithm]

[백준] 4386번 별자리 만들기(크루스칼 알고리즘)(Python - 파이썬)

문제 접근 n개의 별들의 좌표를 입력 받아서 그 별들을 이어 별자리를 만들 수 있는데 별자리를 만드는데 드는 최소 비용을 구해야합니다. 별자리의 조건은 다음과 같습니다. - 별자리를 이루는 선은 서로 다른 두별을 일직선으로 이은 형태이다. - 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별은 2차원 평면 위에 놓여있고 선을 하나 이을 때 마다 두 별 사이의 거리만큼의 비용이 든다고 합니다. 별자리의 조건 및 문제를 통하여 최소 신장 트리를 구해야한다는 것을 알 수 있습니다. 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구하였습니다. 2022.03.06 - [정보[Information]] - 신장 트리(Spanning Tree) / 크루스칼 알고리즘(Kruskal Algo..

2022. 3. 11. 16:40
알고리즘 문제풀이[Algorithm]

[백준] 1922번 네트워크 연결(크루스칼 알고리즘)(Kruskal Algorithm)(Python - 파이썬)

백준 1922번 문제입니다. (solved.ac)기준 골드 4 문제입니다. https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.www.acmicpc.net 문제 접근 모든 컴퓨터가 연결되어 있어야하고 최소 비용으로 모든 컴퓨터를 연결하기를 원한다고 합니다.단, a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있다면 a와 c가 연결된다고 합니다. ex) a - b - c최소 신장 트리를 구하는 간단한 문제입니다. 저는 크루스칼 알고리즘을 통하여 구현해보았습니다.크루스칼 알고리즘은 아래 링크에 설명되어있습니다. 2022.03.06 - [정보[Information..

2022. 3. 9. 15:09
정보[Information]

신장 트리(Spanning Tree) / 크루스칼 알고리즘(Kruskal Algorithm)(Python - 파이썬)

서로소 집합 자료구조, 합집합-찾기 자료구조 개념이 필요하기 때문에 잘 모른다면 아래에서 읽어보고 오는 것이 좋다. 2022.03.05 - [정보[Information]] - 서로소 집합 자료구조(Union-Find)(Python-파이썬) 서로소 집합 자료구조(Union-Find)(Python-파이썬) 서로소 집합(Disjoint Sets) 수학에서 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 집합 {1,2} 와 집합 {3,4}는 서로소 관계이다. 반면에 집합 {1,2}와 집합 {2,3}은 2라는. soopeach.tistory.com 신장 트리 신장 트리는 그래프 알고리즘 문제로 자주 출제되는 문제 유형이다. 기본적으로 신장 트리(Spanning Tree..

2022. 3. 6. 17:20