SK_MOUSE 개발일기

先요약 일반적인 그래프를 구성할때는 싸이클이 있는지를 확인한다 : findParent 메소드 이용 두개의 노드를 간선으로 잇는 작업은 unionParent 메소드를 이용한다. 신장트리는 싸이클이 없어야하며, 모든 노드가 연결되어있어야한다 : 크루스칼 알고리즘으로 만든다. 위상정렬은 싸이클이 없고 방향그래프(DAG)인 상황에, 방향성에 거스르지 않도록 순서대로 나열하는 것. 그래프의 기본적인 이론에 대하여 알아보겠다. 아래의 메소드는 그래프 문제를 풀때 구현해놓으면 좋은 메소드이다. 1. findParent(int x) 메소드 : 루트노드가 아니라면, 해당 루트 노드를 찾을때까지 재귀적으로 findParent메소드 재귀호출. ex) findParent(3번노드) -> 재귀 findParent(2번노드) -..

(크루스칼알고리즘)주어진 모든 간선을 비용을 기준으로 오름차순 정렬한다.(PriorityQueue사용) 간선의 부모 노드를 기록한다. 싸이클이 만들어지지 않게 부모노드를 체크하며 간선을 연결한다. => Union 알고리즘을 이용한다! import java.util.*; class Solution { class Edge implements Comparable { int from, to, cost; Edge(int from, int to, int cost){//간선문제는 from to를 만들어주는것이 좋다. this.from = from; this.to = to; this.cost = cost; } @Override public int compareTo(Edge o){ return this.cost - o...