오늘의 코테 문제

섬 연결하기 프로그래머스

MST(Minimum Spanning Tree)를 구하는 문제!

MST란?

• 노드를 전부 있는다. 하지만 사이클은 없어야 한다.
• 정점이 v개이면 간선의 수는 v-1이다.
• 크루스칼 알고리즘을 통해 구할 수 있다.

크루스칼 알고리즘(Kruskal Algorithm)

• 간선들을 중심으로, 그리디 알고리즘을 통해 최소 스패닝 트리를 구하는 알고리즘이다.

1. 선택하지 않은 간선 중 최소 가중치의 간선을 선택한다.(간선의 가중치를 기준으로 오름차순정렬을 수행한다.)
2. 사이클이 없는 경우에만 선택한다.(1-> 3-> 5-> 1이렇게 사이클이 돌면 안됨)
3. v-1(정점개수 -1)간선이 선택될 때 까지 반복한다.

Union-find 합집한 찾기 -> 대표적인 그래프 알고리즘

• find: x가어떤 집합에 포함되어 있는지 check한다.

어떤 존잘님의 코드를 분석해본 것 아직 공부가 더 필요한 것 같다. ㅠ

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL