본문 바로가기

크루스칼

[BOJ] 백준 1414번 불우이웃돕기 (Java)
Dot Algo∙ DS/PS 2022. 3. 13. [BOJ] 백준 1414번 불우이웃돕기 (Java) #1414 불우이웃돕기 난이도 : 골드 2 유형 : 문자열 / MST / 크루스칼 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net ▸ 문제 다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다. 다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때,..
[BOJ] 백준 2887번 행성 터널 (Java)
Dot Algo∙ DS/PS 2021. 11. 28. [BOJ] 백준 2887번 행성 터널 (Java) #2887 행성 터널 난이도 : 골드 1 유형 : 그래프 탐색 / 최소 스패닝 트리(MST) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net ▸ 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 m..
[BOJ] 백준 17472번 다리 만들기 2 (Java)
Dot Algo∙ DS/PS 2021. 6. 10. [BOJ] 백준 17472번 다리 만들기 2 (Java) #17472 다리 만들기 2 난이도 : 골드 2 유형 : 그래프 탐색/ BFS/ 최소 신장 트리 (MST) - 크루스칼 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net ▸ 문제 ▸ 입력 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. ▸ 출력 모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1..
[알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로
Dot Algo∙ DS/알고리즘 개념 2021. 4. 29. [알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로 그리디 알고리즘 과정 해 선택 실행 가능성 검사 해 검사 크루스칼(Kruskal)과 그리디 알고리즘 최소 신장트리는 사이클을 형성하지 않고 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리이다. 최소 신장 트리를 구축하는데 한 가지 중요한 제약은 최소 신장 트리 내에 사이클이 형성되어서는 안된다는 것이다. 크루스칼 알고리즘 동작 방식 1) 그래프 내의 모든 간선의 가중치에 대해 오름차순으로 정렬한다. 2) 1)의 간선을 차례대로 순회하면서 최소 신장 트리에 추가한다. (사이클 생성 x) 그리디 과정으로 다시 보면 다음과 같다. 해 선택 : 가장 작은 가중치의 간선 선택 실행 가능성 검사 : 사이클 생성 여부 파악 (사이클 생성되면 x) 해 검사 : 모든 정점이 하나의 집합에 있는지 확인 다익스트라(..

티스토리툴바

티스토리툴바