2. 'Hyper-V 빨리 만들기'로 가면 MS 홈페이지에서 받을 수 있는 윈도우 이미지를 받을 수 있다. 여기서 받을 수 있는 이미지는 윈도우와 우분투다. 당연히 윈도우는 체험판으로 정식 버전 활성화를 위해서는 별도의 시리얼키를 가지고 있어야 한다. 즉, 호스트 윈도우, 게스트 윈도우 이렇게 적어도 2개의 라이센스가 필요하다.
하지만 이미 받아놨다면 관리자에서 불러와서 실행하면 된다.
주의 : 가상이미지 만들 때 '1세대' '2세대'가 나오는데 '1세대'로 할 것! 2세대 호환성이 안 좋아서 결국 1세대로 설치했다.
가상 머신 인터넷 사용하기
기본적으로 Hyper-V는 Parallels나 VMware Workstation와 같은 일반 컴퓨터용으로 개발된 가상화 솔루션이 아니라 VMware ESXi와 같은 워크스테이션용으로 개발된 가상화 솔루션이라 인터넷 연결이 끊어져있다. (VMware ESXi도 기본으로 인터넷 연결을 끊어 놓는지는 모르겠다. VMware ESXi도 무료니까 누군가 받아서 실험을...)
따라서 가상 머신에 인터넷을 이용하기 위해서는 몇 가지 설정이 필요하다.
'Hyper-V 관리자'> 우측 탭에서 '가상 스위치 관리자...'
'새 가상 네트워크 스위치' > '내부' > '가상 스위치 만들기'
이름을 정하고, 연결 형식에 '외부 네트워크'에서 호스트 OS에 설치된 물리 네트워크 카드를 선택 > '적용'
가상 머신을 선택하면 우측 탭에 해당 가상 머신의 '설정' 옵션이 뜬다. 혹은 가상 머신을 우클릭 한 다음 '설정'으로 들어간다.
'네트워크 어댑터' > '가상 스위치'에서 방금 만든 어댑터를 설정 후 '적용'
이제 가상 머신에서 호스트를 공유해 외부 인터넷이 된다.
빠르다... 하지만...
Hyper-V가 거의 Parallels 급으로 빠르다. Cinebench R20을 돌려봤을 때 호스트에서 760점, 게스트에서 700점이 나오니 무려 92%의 효율을 보인다. 게다가 그래픽 가속도 생각보다 좋아 조작에 큰 불편함이 없다. 역시 Azure (애저)에서 사용하기 위해 만들어서 그런가보다. 문제는 편의기능이 떨어져도 너무 떨어진다. 정말 그냥 독립된 운영체제 하나 설치하기에는 빠르고 좋지만, 호스트와 파일을 공유하고 USB를 마운트 하는 등... 안되는 것이 너무 많다.(방법이 있을 것 같긴 한데... 기본 설정을 대충 봐서는 없어보인다... 그렇다고 구글링까지 해가며 찾기엔... 그냥 VMware를 설치하고 말지...) 그래서 저는 결국 VMware로 넘어갑니다. VMware를 쓰면 Parallels에서 쓰던 '동시 실행 모드'와 같은 기능인 Unity??인가도 쓸 수 있고...
- 추가 -
VMware도 게스트에서 700점이 나오니... 사실상 Hyper-V가 속도 면에서는 이점이 없네요. 게다가 그래픽 가속이 VMware쪽이 더 뛰어나서 체감 성능도 더 좋고... 편리함은 뭐 더할 나위 없이 좋구요. 물론... Parallels의 96~99%의 효율은 아니더라도 92%가 어디인가요...
맥에선 부트캠프와 거의 대등한 성능 보이는 Parallels와 달리 VMware Fusion은 어떤 때는 50% 효율까지 떨어져서 50~85%의 낮은 성능 효율을 보일 뿐 아니라, 배터리 효율 마저 나쁘다 보니 Parallels와 체감 차이가 너무도 커서 도저히 못 쓰겠어서 Parallels만 썼는데 윈동용 VMware는 좋네요 -_-;;
import java.util.Comparator;
import java.util.Objects;
import java.util.SortedSet;
import java.util.TreeSet;
class Employee implements Comparable<Employee> {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
// Two Employees are equal if their IDs are equal
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee employee = (Employee) o;
return id == employee.id;
}
@Override
public int hashCode() {
return Objects.hash(id);
}
// Compare employees based on their IDs
@Override
public int compareTo(Employee employee) {
return this.getId() - employee.getId();
}
@Override
public String toString() {
return "Employee{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
public class TreeSetUserDefinedObjectExample {
public static void main(String[] args) {
// Creating a TreeSet of User Defined Objects.
/*
The requirement for a TreeSet of user defined objects is that
1. Either the class should implement the Comparable interface and provide
the implementation for the compareTo() function.
2. Or you should provide a custom Comparator while creating the TreeSet.
*/
SortedSet<Employee> employees = new TreeSet<>();
// TreeSet uses the compareTo() method of the Employee class to compare two employees and sort them
employees.add(new Employee(1010, "Rajeev"));
employees.add(new Employee(1005, "Sachin"));
employees.add(new Employee(1008, "Chris"));
System.out.println("Employees (sorted based on Employee class's compareTo() function)");
System.out.println(employees);
// Providing a Custom Comparator (This comparator compares the employees based on their Name)
employees = new TreeSet<>(Comparator.comparing(Employee::getName));
employees.add(new Employee(1010, "Rajeev"));
employees.add(new Employee(1005, "Sachin"));
employees.add(new Employee(1008, "Chris"));
System.out.println("\nEmployees (sorted based on the supplied Comparator)");
System.out.println(employees);
}
}
// 결과
# Output
Employees (sorted based on Employee class's compareTo() function)
[Employee{id=1005, name='Sachin'}, Employee{id=1008, name='Chris'}, Employee{id=1010, name='Rajeev'}]
Employees (sorted based on the supplied Comparator)
[Employee{id=1008, name='Chris'}, Employee{id=1010, name='Rajeev'}, Employee{id=1005, name='Sachin'}]
<!DOCTYPE html>
<head>
<title>Home</title>
</head>
<body>
<h1>
Hello world!
</h1>
<%
int a = 10;
int b = 5;
int c = a + b;
// jsp 안에 java코드 사용(이제는 하지 말 것)
// jstl : jsp에서 태그 <> 형태로 제공하는 기능 (jsp 기반)(한국은 아직 여기...)
// thymeleaf (<html> 기반) (spring boot 기본 방식 가장 최신이고 표준이다.)
%>
<P> axb+c=<%=a*b+c %>. </P> <!-- 대문자로 써도 되긴 하지만 html 표준은 태그를 소문자로 사용한다. <p> 이런식으로 사용 -->
</body>
</html>
이렇게 <% %> 사이에 자바 코드를 넣을 수 있다. (<!-- --> 사이에 주석을 넣을 수 있는 것처럼...)
하지만 매우매우 옛날 방식이다. 20~15년 전 사용되던 방식이라고 한다. HTML은 코드에 모든게 다 드러나기 때문에 자바 코드를 그대로 사용하면 보안에 치명적이기 때문이다. 다만... 외국 기준이고.... IT 기술에 뒤쳐진 한국에서는 5년 전 까지도 이대로 유지보수 되는 곳이 있었다고... 지금도 있을지 모른다고 한다 -_-;;
절대 사용하지는 말되 혹시 이런게 나오면 아... 자바코드구나... 하고 사용하진 말라고...
@RequestMapping(value = "/", method = RequestMethod.GET)
public String home(Locale locale, Model model) {
DB db = new DB<Memo>("/Users/saebyul/SqliteDB/0916memo.db", "memo");
model.addAttribute("test", new Memo()); // jsp파일. 즉, HTML에서 객체를 사용하기 위해 test라는 변수에 담아 넘겨준다.
if (db.open()) {
ArrayList<Memo> list = db.selectData(new Memo());
model.addAttribute("list", list);
db.close();
}
return "home";
}
home.jsp
<%@ page language="java" contentType="text/html; charset=UTF-8"
pageEncoding="UTF-8"%>
<%@ taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %>
<%@ page session="false" %>
<!DOCTYPE html>
<head>
<title>Home</title>
</head>
<body>
<!-- test라는 변수가 HomeController에게 Memo라는 객체를 넘겨 받아 그 객체의 title, memo 안에 원하는 value를 넣는다. -->
<c:set target="${test }" property="title" value="야호호호"></c:set>
<c:set target="${test }" property="memo" value="코로나야끝나라아아아"></c:set>
<p> title : <c:out value="${test.title }"></c:out> </p>
<p> memo : <c:out value="${test.memo }"></c:out> </p>
<table style="width: 100%;">
<tbody>
<c:forEach var="each" items="${list }">
<tr>
<td>${each.getIdx() }</td> <!-- getter를 쓸 수도 있고, -->
<td>${each.title }</td> <!-- c:out 태그를 생략하고 사용할 수도 있다. (편리!) -->
<td><c:out value="${each.memo }"></c:out></td> <!-- Full로 쓰면 c:out 태그를 넣어야 한다. -->
<td><a href="u1?idx=${each.idx }">수정하기</a>
</tr>
</c:forEach>
</tbody>
</table>
</body>
</html>
지금 여기 2가지가 있는데,
<!-- test라는 변수가 HomeController에게 Memo라는 객체를 넘겨 받아 그 객체의 title, memo 안에 원하는 value를 넣는다. -->
<c:set target="${test }" property="title" value="야호호호"></c:set>
<c:set target="${test }" property="memo" value="코로나야끝나라아아아"></c:set>
<p> title : <c:out value="${test.title }"></c:out> </p>
<p> memo : <c:out value="${test.memo }"></c:out> </p>
이 부분은 홈컨트롤러로부터 Memo라는 객체를 test라는 변수로 넘겨 받아, setter, getter를 이용해 객체를 활용하는 것이다. 이때 C 태그를 이용했다.
주의 : new Memo()라는 객체를 넘겨받았다. 값이 들어 있는 객체를 받은 것이 아니다.
<table style="width: 100%;">
<tbody>
<c:forEach var="each" items="${list }">
<tr>
<td>${each.getIdx() }</td> <!-- getter를 쓸 수도 있고, -->
<td>${each.title }</td> <!-- c:out 태그를 생략하고 사용할 수도 있다. (편리!) -->
<td><c:out value="${each.memo }"></c:out></td> <!-- Full로 쓰면 c:out 태그를 넣어야 한다. -->
<td><a href="u1?idx=${each.idx }">수정하기</a>
</tr>
</c:forEach>
</tbody>
</table>
이 부분은 홈컨트롤러가 DB한테 selectData 메소드를 실행시켜 데이터베이스로부터 쿼리를 받아 ArrayList 안에 Memo 객체를 넣어 list라는 변수로 넘겨 받아 for each를 이용해 테이블을 출력하는 것이다.
<c:out value="${each.memo }"></c:out> 이렇게 C태그 getter를 이용할 수도 있고,
${each.title } 그냥 이렇게 C태그를 생략할 수도 있으며
${each.getIdx() } 이렇게 넘겨 받은 객체에 포함된 getter를 이용할 수도 있다.
물론... 자바 내에서 실행되는게 아니라 객체 내에 getter는 반드시 포함되어 있어야 한다.
7z : 압축도 많이 되고, 64비트에 멀티코어 지원을 잘 해서 좋은데 문제는... 오류정정이 되지 않아 파일이 크고 많아지면..... 좋지 않다...
파일 개수가 수천 개 정도로 적으면 괜찮은데... 10만 단위 급으로 많을 경우 열심히 압축 했는데 제대로 못 푸는 상황이 발생할 가능성이 높다. 심지어 저장모드인데도 오류 발생해서 몇 시간의 노력이 물거품이 되는 것을 몇 번 겪고 나니..... 못 쓰겠다......
zip : 사실... 7z 쓰기 시작한 후로 zip 무시했는데... 범용성은 물론, 안정성에서 zip이 최강이다. bzip도 50만건이 넘어가니 저장모드에서조차 가끔 실패하는 경우가 있는데 zip은... 단 한 번도 실패한 적이 없다. 속도도 너무 느리지 않고... 가장 안정적이고 딱히 모난 구석 없는 최고의 압축인 듯 하다.
tar : 무압축의 대명사... 다른 포맷에서 저장 모드로 해도 tar의 속도를 따라오지는 못한다. 압도적인 속도!! 다만... 문제는 파일이 많아지면 오류가 있다;; 파일이 7z과 마찬가지로 파일이 작고 개수가 적을 때만 쓰는게 좋을 것 같다.
bzip2 : gzip은 사실상 bzip2가 나와서 쓸 일이 없고... 그래서 처음부터 bzip2를 쓴건데 생각보다 안정적이다. 문제는 저장모드로 해도 시간이 꽤나 걸린다;; 저장모드로 해도 용량이 상당히 줄어드는걸 보면 기본적으로 완전 저장모드는 없는 듯 하다. 50만개 이상의 파일도 잘 저장된다.
위 그림에서 보면 좌측의 그래프는 우측의 노란색으로 표시된 것과 같은 8개의 Spanning subtree를 갖는다.
더 큰 그래프를 보면 아래와 같다.
이 그래프의 특징은 모든 꼭짓점을 포함하도록 변이 이어지나, 순환하지 않는다.
Spanning subgraph 의 종류
Spanning subgraph 가운데 r-정규 그래프인 것을 r-factor라고 한다.
0차 인자 : 꼭짓점 집합 위의 무변 그래프. 즉, 그냥 점 하나... 0차원이다.
1차 인자 : 완벽 부합(Perfect matching)이라고 한다.
2차 인자 이상 : 아래 그래프를 확인하자.
페테르센 그래프에서, 붉은 변들은 1차 인자(완벽 부합)를 이루며, 푸른 변들은 2차 인자를 이룬다.
데자르그 그래프에서, 붉은 색의 변들 · 푸른 색의 변들 · 녹색의 변들은 각각 1차 인자(완벽 부합)를 이룬다.
2. Minimum cost spanning tree
여러 꼭짓점(Node, Vertex)과 각 변(Edge)이 있다. 이 모든 꼭짓점을 연결하는 방법(Spanning subtree)는 무수히 많다. 그 중, 변의 비용이 최소가 되는 경우를 '최소 비용 신장 나무(Minimum cost spanning tree)'라 한다.
이를 증명하려면 '선택 공리'가 필요하다는데... 수학과가 아니니 넘어가도록 한다.
이러한 그래프에서 최소 비용을 찾는 대표적인 알고리즘이 Prim's Algorithm(프림 알고리즘)과 Kruskal' Algorithm(크러스컬 알고리즘)이 있다.
꼭짓점의 개수를 V, 변의 개수를 E라고 할 때,
프림 알고리즘은 Binary heap(이진 힙)을 이용해 O(E log V)의 시간복잡도를 가지고, 그래프가 충분히 빽빽한 경우(E = Ω(V log V))에는 Fibonacci heap(피보나치 힙)을 이용해 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 O(E + V log V)까지 떨어진다.
또한, 크러스컬 알고리즘은 O (E log V)의 시간 복잡도를 갖는다.
음... 솔직히 무슨 말인지 잘 모르겠다 -_-;; 이진 로그인지, 자연 로그인지, 상용 로그인지 설명도 없고... 수학과면 뭔지 알겠지만... 아마 사용로그 같기는 한데..... 그냥 비교 설명이 잘 된 블로그를 하나 소개한다.
크러스컬은 평균적이고, 프림은 코드를 얼마나 효율적으로 짰는지에 따라 효율이 극대화 되거나 극악이 된다.
이론적으로는 '엣지 >> 노드'인 경우 프림이 훨씬 빠르지만 잘못 짜면 망한다... 그래서 알고리즘 메달리스트들은 크러스컬만 쓴다고...
We can achieve this bound as follows: first sort the edges by weight using a comparison sort in O(E log E) time; this allows the step "remove an edge with minimum weight from S" to operate in constant time. Next, we use a disjoint-set data structure to keep track of which vertices are in which components. We place each vertex into its own disjoint set, which takes O(V) operations. Finally, in worst case, we need to iterate through all edges, and for each edge we need to do two 'find' operations and possibly one union. Even a simple disjoint-set data structure such as disjoint-set forests with union by rank can perform O(E) operations in O(E log V) time. Thus the total time is O(E log E) = O(E log V).
뭔소리죠...?
코드 최적화... 이 압축하는게 그림으로 볼 때 그래프의 모양(MST)이 바뀌는 것은 아니다. 단, 컴퓨터라 사람처럼 한 눈에 볼 수 없어 '자식 - 부모'의 노드 관계를 구하기 위해서는 '1 - 3 - 5 - 7' 이라는 그래프에서 7의 부모를 찾기 위해서 5를 찾고, 다시 5의 부모가 있는지 찾기 위해서 3을 찾고.. 이런식으로 3번 재귀함수를 돌아야 한다. 이게 꼭짓점이 많아지고, 노드가 일렬로 이어지면 시간복잡도가 매우 높아지기 때문에 재귀에서 return이 될 때 3, 5, 7의 부모를 모두 1이라 업데이트를 해준다.
Kruskal.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Kruskal {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static PriorityQueue<Edge> pq; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = sc.nextInt();
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = sc.nextInt();
mst = new ArrayList<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
// Queue는 기본적으로 FIFO 구조를 갖는다. Priority queue는 '최대 우선순위 큐'와 '최소 우선순위 큐'로 나뉜다.
pq = new PriorityQueue<>();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
// 각 vertex는 시작할 때는 자기 자신을 root로 초기화.
arr[i] = i;
}
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
for (int i = 0; i < E; i++) {
int v1 = sc.nextInt(); // 1번 노드와... 1번 노드와
int v2 = sc.nextInt(); // 2번 노드의... 3번 노드의
int value = sc.nextInt(); // 비용은 5다... 비용은 4다
// 우선순위 큐에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
pq.add(new Edge(v1, v2, value));
}
// V개의 노드를 연결하는 최소 Edge의 수는 '노드-1'이므로 mst.size()가 'V-1'이 될 때까지 반복한다.
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
while(mst.size() < (V-1)) {
// PQ에 하나씩 넣었고, 이제 하나씩 뺀다. PQ로 넣어서 FIFO이 아닌 오름차순으로 나온다.(value 기준)
Edge edge = pq.poll();
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
if(find(edge.start)!=find(edge.end))
{
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 MST ArrayList에 Edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(edge.start, edge.end);
}
}
System.out.println(mst);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int n1, int n2) {
int p1 = find(n1); // p1 : n1의 부모, n1 : 앞쪽 인자 node
int p2 = find(n2); // p2 : n2의 부모, n2 : 뒤쪽 인자 node
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}
/*
6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
4 6 8
3 5 11
4 5 3
5 6 8
*/
// source : https://velog.io/@dudrkdl777/Graph-최소신장트리-MSTKruskal알고리즘
수업때 한 원본 소스...
여기서 보면 union 함수 안에
if (p1 != p2) {
arr[p1]= p2;
}
이 부분이 Path Compression(경로 압축)을 하는 과정... 즉, 코드 최적화다.
Kruskal2.java
// 기존 1번 코드 원본에서 불필요하게 반복되는 find 함수의 실행을 줄임.
import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Kruskal2 {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static PriorityQueue<Edge> pq; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
long startTime = System.nanoTime();
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = sc.nextInt();
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = sc.nextInt();
mst = new ArrayList<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
// Queue는 기본적으로 FIFO 구조를 갖는다. Priority queue는 '최대 우선순위 큐'와 '최소 우선순위 큐'로 나뉜다.
pq = new PriorityQueue<>();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
// 각 vertex는 시작할 때는 자기 자신을 root로 초기화.
arr[i] = i;
}
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
for (int i = 0; i < E; i++) {
int v1 = sc.nextInt(); // 1번 노드와... 1번 노드와
int v2 = sc.nextInt(); // 2번 노드의... 3번 노드의
int value = sc.nextInt(); // 비용은 5다... 비용은 4다
// 우선순위 큐에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
pq.add(new Edge(v1, v2, value));
}
// V개의 노드를 연결하는 최소 Edge의 수는 '노드-1'이므로 mst.size()가 'V-1'이 될 때까지 반복한다.
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
while(mst.size() < (V-1)) {
// PQ에 하나씩 넣었고, 이제 하나씩 뺀다. PQ로 넣어서 FIFO이 아닌 오름차순으로 나온다.(value 기준)
Edge edge = pq.poll();
// Edge의 양 끝 각 노드(start, end라 명명함)의 최종 부모(root)를 구한다.
int parentEdgeStart = find(edge.start);
int parentEdgeEnd = find(edge.end);
// int parentEdgeStart = -1;
// int parentEdgeEnd = -1;
// // 기본 변수 타입인 int는 null을 받아들일 수 없다. edge 객체의 int 변수를 Integer로 바꿨다.
// // 의미가 있는지는 모르겠음. 그냥 위에 바로 int에 find 돌려서 넣고 edge 인스턴스 변수는 그대로 int로 해도 될 것 같은데...
// if (edge.start != null && edge.end != null) {
// parentEdgeStart = find(edge.start);
// parentEdgeEnd = find(edge.end);
// }
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
if(parentEdgeStart != parentEdgeEnd)
{
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(parentEdgeStart, parentEdgeEnd);
}
}
System.out.println(mst);
long endTime = System.nanoTime(); // (종료점)
long timeInterval = (endTime - startTime) / 1000000; // (시간차)
System.out.printf("Code Time : %d (ms) \n", timeInterval);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int p1, int p2) {
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
// Integer start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}
MST를 구할 때마다 union함수 내에서 find 함수를 불필요하게 다시 호출하는 문제가 있어 해당 로직을 줄였다.
Kruskal3.java
// 2번 코드에서 Scanner를 BufferedReader, InputStreamReader로 바꿈.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Kruskal3 {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static PriorityQueue<Edge> pq; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
// throws IOException을 해주거나,
// String var = null; 을 미리 인스턴스화 시킨 후
// try {
// var = bufferedReader.readLine();
// } catch (IOException | NumberFormatException e) {
// e.printStackTrace();
// }
// 을 해줘야한다.
long startTime = System.nanoTime();
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = Integer.parseInt(bufferedReader.readLine());
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = Integer.parseInt(bufferedReader.readLine());
mst = new ArrayList<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
// Queue는 기본적으로 FIFO 구조를 갖는다. Priority queue는 '최대 우선순위 큐'와 '최소 우선순위 큐'로 나뉜다.
pq = new PriorityQueue<>();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
// 각 vertex는 시작할 때는 자기 자신을 root로 초기화.
arr[i] = i;
}
// Edge의 정보는 양쪽 Vertex와 비용, 3개의 정보만 고정적으로 존재하기 때문에 3으로 고정 선언.
String[] inputTmp = new String[3];
int v1;
int v2;
int value;
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
for (int i = 0; i < E; i++) {
inputTmp = bufferedReader.readLine().split(" ");
v1 = Integer.parseInt(inputTmp[0]); // 1번 노드와... 1번 노드와
v2 = Integer.parseInt(inputTmp[1]); // 2번 노드의... 3번 노드의
value = Integer.parseInt(inputTmp[2]); // 비용은 5다... 비용은 4다
// 우선순위 큐에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
pq.add(new Edge(v1, v2, value));
}
// V개의 노드를 연결하는 최소 Edge의 수는 '노드-1'이므로 mst.size()가 'V-1'이 될 때까지 반복한다.
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
while(mst.size() < (V-1)) {
// PQ에 하나씩 넣었고, 이제 하나씩 뺀다. PQ로 넣어서 FIFO이 아닌 오름차순으로 나온다.(value 기준)
Edge edge = pq.poll();
// Edge의 양 끝 각 노드(start, end라 명명함)의 최종 부모(root)를 구한다.
int parentEdgeStart = find(edge.start);
int parentEdgeEnd = find(edge.end);
// int parentEdgeStart = -1;
// int parentEdgeEnd = -1;
// // 기본 변수 타입인 int는 null을 받아들일 수 없다. edge 객체의 int 변수를 Integer로 바꿨다.
// // 의미가 있는지는 모르겠음. 그냥 위에 바로 int에 find 돌려서 넣고 edge 인스턴스 변수는 그대로 int로 해도 될 것 같은데...
// if (edge.start != null && edge.end != null) {
// parentEdgeStart = find(edge.start);
// parentEdgeEnd = find(edge.end);
// }
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
if(parentEdgeStart != parentEdgeEnd)
{
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(parentEdgeStart, parentEdgeEnd);
}
}
bufferedReader.close();
System.out.println(mst);
long endTime = System.nanoTime(); // (종료점)
long timeInterval = (endTime - startTime) / 1000000; // (시간차)
System.out.printf("Code Time : %d (ms) \n", timeInterval);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int p1, int p2) {
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
// Integer start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}
위 2번 코드에서 Scanner를 BufferedReader, InputStreamReader로 바꿨다.
// 3번 코드에서 ArrayList<Edge> mst를 HashSet<Edge>로, PriorityQueue<Edge> pq를 TreeSet<Edge>로 바꿈.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.TreeSet;
public class Kruskal4 {
static int V, E; // V : 점, E : 변
static HashSet<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static TreeSet<Edge> ts; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
long startTime = System.nanoTime();
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = Integer.parseInt(bufferedReader.readLine());
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = Integer.parseInt(bufferedReader.readLine());
mst = new HashSet<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
ts = new TreeSet();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
arr[i] = i;
}
// Edge의 정보는 양쪽 Vertex와 비용, 3개의 정보만 고정적으로 존재하기 때문에 3으로 고정 선언.
String[] inputTmp = new String[3];
int v1;
int v2;
int value;
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
for (int i = 0; i < E; i++) {
inputTmp = bufferedReader.readLine().split(" ");
v1 = Integer.parseInt(inputTmp[0]); // 1번 노드와... 1번 노드와
v2 = Integer.parseInt(inputTmp[1]); // 2번 노드의... 3번 노드의
value = Integer.parseInt(inputTmp[2]); // 비용은 5다... 비용은 4다
// TreeSet에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
ts.add(new Edge(v1, v2, value));
}
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
while(mst.size() < (V-1)) {
// TreeSet 잘 될까!?
Edge edge = ts.pollFirst();
int parentEdgeStart = find(edge.start);
int parentEdgeEnd = find(edge.end);
if(parentEdgeStart != parentEdgeEnd) {
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(parentEdgeStart, parentEdgeEnd);
}
}
bufferedReader.close();
System.out.println(mst);
long endTime = System.nanoTime(); // (종료점)
long timeInterval = (endTime - startTime) / 1000000; // (시간차)
System.out.printf("Code Time : %d (ms) \n", timeInterval);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int p1, int p2) {
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) { return this.value - o.value; }
@Override
public String toString() { return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n"; }
}
}
3번 코드에서 ArrayList<Edge> mst를 HashSet<Edge>로, PriorityQueue<Edge> pq를 TreeSet<Edge>로 바꿨다.
// 3번 코드에서 ArrayList<Edge> mst와 PriorityQueue<Edge> pq를 모두 TreeSet<Edge>로 바꿈.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
public class Kruskal5 {
static int V, E; // V : 점, E : 변
static TreeSet<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static TreeSet<Edge> ts; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
long startTime = System.nanoTime();
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = Integer.parseInt(bufferedReader.readLine());
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = Integer.parseInt(bufferedReader.readLine());
mst = new TreeSet<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
ts = new TreeSet<>();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
arr[i] = i;
}
// Edge의 정보는 양쪽 Vertex와 비용, 3개의 정보만 고정적으로 존재하기 때문에 3으로 고정 선언.
String[] inputTmp = new String[3];
int v1;
int v2;
int value;
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
for (int i = 0; i < E; i++) {
inputTmp = bufferedReader.readLine().split(" ");
v1 = Integer.parseInt(inputTmp[0]); // 1번 노드와... 1번 노드와
v2 = Integer.parseInt(inputTmp[1]); // 2번 노드의... 3번 노드의
value = Integer.parseInt(inputTmp[2]); // 비용은 5다... 비용은 4다
// TreeSet에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
ts.add(new Edge(v1, v2, value));
}
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
while(mst.size() < (V-1)) {
// TreeSet 잘 될까!?
Edge edge = ts.pollFirst();
int parentEdgeStart = find(edge.start);
int parentEdgeEnd = find(edge.end);
if(parentEdgeStart != parentEdgeEnd) {
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(parentEdgeStart, parentEdgeEnd);
}
}
bufferedReader.close();
System.out.println(mst);
long endTime = System.nanoTime(); // (종료점)
long timeInterval = (endTime - startTime) / 1000000; // (시간차)
System.out.printf("Code Time : %d (ms) \n", timeInterval);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int p1, int p2) {
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) { return this.value - o.value; }
@Override
public String toString() { return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n"; }
}
}
3번 코드에서 ArrayList<Edge> mst와 PriorityQueue<Edge> pq를 모두 TreeSet<Edge>로 바꿨다.
참고 : 2 ~ 5번 코드에 보면 시간 측정 로직이 들어갔는데, 시작시간이 내가 지정한 시점에서 시작되지 않고, new Scanner(System.in);나 new BufferedReader(new InputStreamReader(System.in)); 이쪽에서 System.in이 시작된 때의 시간을 가져와서 제대로 된 시간 측정이 되지 않는다.
