본문 바로가기
반응형

크루스칼 알고리즘3

(Python/🥇4)백준알고리즘 1197번: 최소 스패닝 트리 문제 바로가기 문제: 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력: 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -.. 2023. 7. 26.
Union-Find (Disjoint Sets) 알고리즘 Union - Find랑 크루스칼 알고리즘을 사용하려면 필수적으로 알아야하는 알고리즘이다. 여러개의 노드가 존재할때 두 개의 노드를 선택하여 같은 트리에 포함되어있는지 확인하는 것이다. Union - Find 를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다. 트리로 부분집합을 표현하고 find를 통해 루트 노드를 찾고 union으로 트리를 합친다. 처음 시작할때 숫자들은 자기 자신이 부모이며, 노드가 연결되어있어 합치게 되면 더 작은값이 부모가 된다. 만약 1,2 가 연결되어있으면 부모는 1,1 이다. def find(parent, x): if parent[x] != x: # 자기 자신이 아닌경우 다른 노드에 연결된 경우 parent[x] = find(parent, parent[x]) retur.. 2023. 6. 13.
(Python/LV3) 섬 연결하기 문제 출처: 프로그래머스 LV3 탐욕범 섬 연결하기 풀이: 문제설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에.. 2023. 5. 23.
반응형

티스토리툴바