위상정렬

문제 링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 위상정렬을 활용해서 문제를 풀이했다. 위상정렬이란? - 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘 - 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' - 기본 조건으로 위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프이다. * 진입차수(Indegree) : 특정한 노드로 들어오는 ..

신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 크루스칼 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데 대표적인 최소 신장 트리 알고리즘이 '크루스칼 알고리즘'이다. 최소 신장 트리는 일종의 트리 자료구조이므로, 최종적으로 신장 트리에 포함되는 간선의 개수가 '노드의 개수 - 1'과 같다는 특징이 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. [알고리즘] 1) 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. 2. 사이클이 발생하는 ..