최소신장트리

[백준] 15591 - MooTube (Silver) (자바 Java)

[Gold V] MooTube (Silver) - 15591 문제 링크 성능 요약 메모리: 299080 KB, 시간: 1452 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다. 농부 존은 모든 MooTube 동영상에 대해 “연관 동영상” 리스트를 만들..

[백준] 2887 - 행성 터널 (자바 Java)

[Platinum V] 행성 터널 - 2887 문제 링크 성능 요약 메모리: 92808 KB, 시간: 1828 ms 분류 그래프 이론(graphs), 최소 스패닝 트리(mst), 정렬(sorting) 문제 설명 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하..

[백준] 1197 - 최소 스패닝 트리 (자바/Java)

[Gold IV] 최소 스패닝 트리 - 1197 문제 링크 성능 요약 메모리: 230420 KB, 시간: 1196 ms 분류 그래프 이론(graphs), 최소 스패닝 트리(mst) 문제 설명 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며,..

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) (자바/Java)

목차 최소 신장 트리 (MST) 신장트리: 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리 최소신장트리: 신장 트리 중에서 사용된 가중치의 합이 최소인 트리 특징 무방향 가중치 그래프 그래프의 가중치 합이 최소여야 한다 N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선을 사용 사이클을 포함하면 안된다. 크루스칼 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 올므차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 (사이클 존재: 대표가 같으면 사이클(Find-Set)) n-1개의 간선이 선택될 때까지 2)를 반복 Kruskal(G) { A