# 크루스칼 알고리즘
[프로그래머스 문제풀이] 29. 섬 연결하기
오랫동안 고민했는데도 문제가 안 풀려서 결국 해답을 찾아봤다. 이 문제는 크루스칼 알고리즘으로 푸는 문제이다. 학교에서 배운 것 같긴 한데 알고리즘 공부를 많이 안 하다보니 어떤 알고리즘인지 잊어먹었다. 그래서 이번 기회에 최소신장트리와 크루스칼 알고리즘의 개념에 대해
[코딩 테스트] - 크루스칼 알고리즘
신장 트리 (Spanning Tree)그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리의 조건이기도 함 최소 신장 트리최소한의 비용으로 구성되는 신장 트리를 찾아야할 때e
(Swift) Programmers 섬 연결하기
코딩테스트 연습 - 섬 연결하기 DFS로 풀기 문제 풀이 아이디어 이 문제는 사실 전형적인 크루스칼 알고리즘 문제입니다. 하지만 문제는 제가 크루스칼 알고리즘을 까먹어 버렸다는 것이죠…😝 그렇다면 푸는 방법이 전혀 없을까요? 어떤 다리를 건설할지는 그리디 알고리즘을 적용해서 비용이 적은 다리부터 건설을 하면 됩니다. 하지만 문제는 비용이 적은 다...
SWEA3124 최소 스패닝 트리
크루스칼 알고리즘을 사용해 구할 수 있다.크루스칼 알고리즘이란 가중치가 가장 작은 간선부터 하나씩 연결해나가는 방식이다.이 문제에서는 정점의 수가 매우 많기 때문에 인접행렬을 사용할 수 없고, Union-Find 알고리즘을 이용해 풀 수 있다.
Kruskal's Algorithm
Kruskal's Algorithm은 가장 적은 비용으로 노드들을 연결하기 위한 알고리즘이다.모든 노드를 최소한의 비용으로 연결시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬하고 비용이 적은 간선부터 차례대로 연결해주면 된다.1\. 정렬된 순서에 맞게 그래프에
무방향 그래프에서의 사이클여부 확인 방법
최근 "최소 스패닝 트리"에 대해 알게되고 해당 문제를 접하게 되었다.당연히 그래프에서 사이클의 존재 여부를 파악하기 위해서는 DFS를 통해 전부 탐색해봐야지만 판단할 수 있다고 생각하고 있었다.그러나 해당 포스트에서는 DFS보다 훨씬 간단하고, 적은 시간이 걸리는 서
이코테_CHAP10. 그래프 이론
서로소 집합 : 공통 원소가 없는 두 집합서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조\-> union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산\-> find 연산 : 특정한 원소가 속한 집합이
[알고리즘] 신장트리(크루스칼 알고리즘)
Spanning Tree, 그래프가 모든 노드가 연결되어 있으면서 사이클이 존재하지 않는 그래프를 의미한다.모든 노드가 연결되어있지만 cycle이 존재하지 않는다는 점에서 tree라 명명하고, 전체 graph에서 부분적으로 신장트리를 도출해낼 수도 있다.이때 한 gra
BOJ - 4386 별자리 만들기
(문제 : https://www.acmicpc.net/problem/4386)조건을 보고 크루스칼 알고리즘을 채택함.1\. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.2\. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져
[알고리즘] 크루스칼 알고리즘
가장 적은 비용(간선연결)을 통해 모든 노드를 연결하는 방법을 도출하는 알고리즘이다.최적의 비용을 도출하는 알고리즘을 공부하는 것부터 시작한다.크루스칼 알고리즘을 구현할 때 만족해야하는 조건이 4가지 존재한다.모든 노드들은 연결되어있는 상태(하나의 graph로 구성)이
17472 다리 만들기 2
굉장히 복합적인 시뮬레이션 문제이다. 다양한 알고리즘을 연습하기에 좋다.https://www.acmicpc.net/problem/17472우선 각각의 섬을 구분할 수 있어야 하므로 섬에 번호를 붙여주어야 한다.반복문을 돌면서 만약 방문하지 않은 섬을 만나면 b