-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path230429.html
More file actions
191 lines (188 loc) · 31 KB
/
230429.html
File metadata and controls
191 lines (188 loc) · 31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>2887번 - 행성 터널</title>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.7.0/styles/default.min.css">
<link href="https://cdn.jsdelivr.net/npm/[email protected]/dist/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-GLhlTQ8iRABdZLl6O3oVMWSktQOp6b7In1Zl3/Jr59b6EGGoI1aFkw7cmDA6j6gD" crossorigin="anonymous">
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/js/bootstrap.bundle.min.js" integrity="sha384-w76AqPfDkMBDXo30jS1Sgez6pr3x5MlQ1ZAGC+nuZB+EYdgRZgiwxhTBTkF7CXvN" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.7.0/highlight.min.js"></script>
<link href="./static/css/main.css" rel="stylesheet">
</head>
<body>
<div class="md-container">
<h2 class="fw-bold" id="번---행성-터널">2887번 - 행성 터널</h2>
<h4 id="분류-그래프-이론-정렬-최소-스패닝-트리">분류 : 그래프 이론,
정렬, 최소 스패닝 트리</h4>
<h4 id="문제">문제</h4>
<p>때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의
행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서
행성을 연결하는 터널을 만들려고 한다.</p>
<p>행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA,
zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|,
|zA-zB|)이다.</p>
<p>민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고
한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는
프로그램을 작성하시오.</p>
<h4 id="풀이">풀이</h4>
<p>모든 정점을 다 방문 가능하게 하는 최소 비용의 간선을 찾는
문제이다.</p>
<p>보통 간선들이 주어지지만 이 문제는 간선이 주어지지 않고</p>
<p>임의의 두 점 사이의 비용을 구하는 식이 주어졌다.</p>
<p>즉, 모든 임의의 두 점에 대해서 연결하는 간선이 존재할 수 있다는
의미이다.</p>
<p>입력의 주어지는 정점의 최대 개수는 10만개이다.</p>
<p>이를 통해 만들 수 있는 간선의 최대 개수는 10C2로 대략 10^10개로
브루트포스하게 풀면 1초안에 들어올 수 없다.</p>
<p>크루스칼을 사용해 문제를 푼다하면 초기 간선을 모두 우선순위 큐에
집어넣어야 하기에 기각했다.</p>
<p>처음에 프림으로 방문하는 정점마다 아직 방문하지 않는 정점의 수 만큼
간선을 만들어 문제 풀이를 시도했으나 메모리 초과가 났다.</p>
<p><strong>어떤 방법을 쓰더라도 간선의 수를 줄일 필요가 있다고
깨달았다.</strong></p>
<p>고민을 해보니 모든 정점 사이에 간선을 설치할 수 있다면 해당 정점에서
각 축에 대해서 양 옆의 정점을 잇는 간선들만 체크하면 된다는 걸
깨달았다.</p>
<p>예를 들어 X축에 대하여 A,B,C 의 정점이 일렬로 있다고 하고 AC를 잇는
간선을 사용하여 가장 비용이 적은 트리를 만들 수 있다고 하자.</p>
<p>이 경우 AC를 잇는 간선을 어짜피 AB,BC 간선으로 대체할 수 있다. 따라서
바로 옆에 있는 간선들만 우선순위 큐에 넣으면 모든 경우의 수에 대해
상정할 수 있다.</p>
<p>따라서 모든 정점에 대해 x,y,z 축에 대해서 양 옆 정점을 잇는 간선들을
우선순위 큐에 모두 집어넣고 크루스칼 알고리즘을 사용하여 문제 풀이를
하였다.</p>
<div class="sourceCode" id="cb1"><pre
class="sourceCode java"><code class="sourceCode java"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">util</span><span class="op">.*;</span></span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a><span class="kw">class</span> <span class="bu">Node</span> <span class="op">{</span></span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> x<span class="op">,</span>y<span class="op">,</span>z<span class="op">,</span>idx<span class="op">;</span></span>
<span id="cb1-5"><a href="#cb1-5" aria-hidden="true" tabindex="-1"></a> <span class="kw">public</span> <span class="bu">Node</span><span class="op">(</span><span class="dt">int</span> x<span class="op">,</span> <span class="dt">int</span> y<span class="op">,</span> <span class="dt">int</span> z<span class="op">,</span> <span class="dt">int</span> idx<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-6"><a href="#cb1-6" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">x</span> <span class="op">=</span> x<span class="op">;</span></span>
<span id="cb1-7"><a href="#cb1-7" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">y</span> <span class="op">=</span> y<span class="op">;</span></span>
<span id="cb1-8"><a href="#cb1-8" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">z</span> <span class="op">=</span> z<span class="op">;</span></span>
<span id="cb1-9"><a href="#cb1-9" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">idx</span> <span class="op">=</span> idx<span class="op">;</span></span>
<span id="cb1-10"><a href="#cb1-10" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-11"><a href="#cb1-11" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb1-12"><a href="#cb1-12" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-13"><a href="#cb1-13" aria-hidden="true" tabindex="-1"></a><span class="kw">class</span> Edge <span class="kw">implements</span> <span class="bu">Comparable</span><span class="op"><</span>Edge<span class="op">>{</span></span>
<span id="cb1-14"><a href="#cb1-14" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> s<span class="op">,</span>d<span class="op">,</span>cost<span class="op">;</span></span>
<span id="cb1-15"><a href="#cb1-15" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-16"><a href="#cb1-16" aria-hidden="true" tabindex="-1"></a> <span class="kw">public</span> <span class="fu">Edge</span><span class="op">(</span><span class="dt">int</span> s<span class="op">,</span> <span class="dt">int</span> d<span class="op">,</span> <span class="dt">int</span> cost<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-17"><a href="#cb1-17" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">s</span> <span class="op">=</span> s<span class="op">;</span></span>
<span id="cb1-18"><a href="#cb1-18" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">d</span> <span class="op">=</span> d<span class="op">;</span></span>
<span id="cb1-19"><a href="#cb1-19" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">cost</span> <span class="op">=</span> cost<span class="op">;</span></span>
<span id="cb1-20"><a href="#cb1-20" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-21"><a href="#cb1-21" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-22"><a href="#cb1-22" aria-hidden="true" tabindex="-1"></a> <span class="at">@Override</span></span>
<span id="cb1-23"><a href="#cb1-23" aria-hidden="true" tabindex="-1"></a> <span class="kw">public</span> <span class="dt">int</span> <span class="fu">compareTo</span><span class="op">(</span>Edge e<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-24"><a href="#cb1-24" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="kw">this</span><span class="op">.</span><span class="fu">cost</span> <span class="op">-</span> e<span class="op">.</span><span class="fu">cost</span><span class="op">;</span></span>
<span id="cb1-25"><a href="#cb1-25" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-26"><a href="#cb1-26" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb1-27"><a href="#cb1-27" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-28"><a href="#cb1-28" aria-hidden="true" tabindex="-1"></a><span class="kw">public</span> <span class="kw">class</span> Main <span class="op">{</span></span>
<span id="cb1-29"><a href="#cb1-29" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span> n<span class="op">;</span></span>
<span id="cb1-30"><a href="#cb1-30" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="bu">List</span><span class="op"><</span><span class="bu">Node</span><span class="op">></span> nodes<span class="op">;</span></span>
<span id="cb1-31"><a href="#cb1-31" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span><span class="op">[]</span> parent<span class="op">;</span></span>
<span id="cb1-32"><a href="#cb1-32" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-33"><a href="#cb1-33" aria-hidden="true" tabindex="-1"></a> <span class="kw">public</span> <span class="dt">static</span> <span class="dt">void</span> <span class="fu">main</span><span class="op">(</span><span class="bu">String</span><span class="op">[]</span> args<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-34"><a href="#cb1-34" aria-hidden="true" tabindex="-1"></a> <span class="bu">Scanner</span> sc <span class="op">=</span> <span class="kw">new</span> <span class="bu">Scanner</span><span class="op">(</span><span class="bu">System</span><span class="op">.</span><span class="fu">in</span><span class="op">);</span></span>
<span id="cb1-35"><a href="#cb1-35" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-36"><a href="#cb1-36" aria-hidden="true" tabindex="-1"></a> n <span class="op">=</span> sc<span class="op">.</span><span class="fu">nextInt</span><span class="op">();</span></span>
<span id="cb1-37"><a href="#cb1-37" aria-hidden="true" tabindex="-1"></a> nodes <span class="op">=</span> <span class="kw">new</span> <span class="bu">ArrayList</span><span class="op"><>();</span></span>
<span id="cb1-38"><a href="#cb1-38" aria-hidden="true" tabindex="-1"></a> parent <span class="op">=</span> <span class="kw">new</span> <span class="dt">int</span><span class="op">[</span>n<span class="op">];</span></span>
<span id="cb1-39"><a href="#cb1-39" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-40"><a href="#cb1-40" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> n<span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb1-41"><a href="#cb1-41" aria-hidden="true" tabindex="-1"></a> <span class="bu">Node</span> node <span class="op">=</span> <span class="kw">new</span> <span class="bu">Node</span><span class="op">(</span>sc<span class="op">.</span><span class="fu">nextInt</span><span class="op">(),</span> sc<span class="op">.</span><span class="fu">nextInt</span><span class="op">(),</span> sc<span class="op">.</span><span class="fu">nextInt</span><span class="op">(),</span> i<span class="op">);</span></span>
<span id="cb1-42"><a href="#cb1-42" aria-hidden="true" tabindex="-1"></a> nodes<span class="op">.</span><span class="fu">add</span><span class="op">(</span>node<span class="op">);</span></span>
<span id="cb1-43"><a href="#cb1-43" aria-hidden="true" tabindex="-1"></a> parent<span class="op">[</span>i<span class="op">]</span> <span class="op">=</span> i<span class="op">;</span></span>
<span id="cb1-44"><a href="#cb1-44" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-45"><a href="#cb1-45" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-46"><a href="#cb1-46" aria-hidden="true" tabindex="-1"></a> <span class="bu">System</span><span class="op">.</span><span class="fu">out</span><span class="op">.</span><span class="fu">println</span><span class="op">(</span><span class="fu">solution</span><span class="op">());</span></span>
<span id="cb1-47"><a href="#cb1-47" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-48"><a href="#cb1-48" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-49"><a href="#cb1-49" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span> <span class="fu">solution</span><span class="op">()</span> <span class="op">{</span></span>
<span id="cb1-50"><a href="#cb1-50" aria-hidden="true" tabindex="-1"></a> <span class="bu">PriorityQueue</span><span class="op"><</span>Edge<span class="op">></span> priorityQueue <span class="op">=</span> <span class="kw">new</span> <span class="bu">PriorityQueue</span><span class="op"><>();</span></span>
<span id="cb1-51"><a href="#cb1-51" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-52"><a href="#cb1-52" aria-hidden="true" tabindex="-1"></a> <span class="fu">settings</span><span class="op">(</span>priorityQueue<span class="op">);</span></span>
<span id="cb1-53"><a href="#cb1-53" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> cost <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb1-54"><a href="#cb1-54" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-55"><a href="#cb1-55" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span> <span class="op">(</span>priorityQueue<span class="op">.</span><span class="fu">size</span><span class="op">()</span> <span class="op">></span> <span class="dv">0</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-56"><a href="#cb1-56" aria-hidden="true" tabindex="-1"></a> Edge e <span class="op">=</span> priorityQueue<span class="op">.</span><span class="fu">poll</span><span class="op">();</span></span>
<span id="cb1-57"><a href="#cb1-57" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-58"><a href="#cb1-58" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span><span class="fu">find</span><span class="op">(</span>e<span class="op">.</span><span class="fu">s</span><span class="op">)</span> <span class="op">==</span> <span class="fu">find</span><span class="op">(</span>e<span class="op">.</span><span class="fu">d</span><span class="op">))</span></span>
<span id="cb1-59"><a href="#cb1-59" aria-hidden="true" tabindex="-1"></a> <span class="cf">continue</span><span class="op">;</span></span>
<span id="cb1-60"><a href="#cb1-60" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-61"><a href="#cb1-61" aria-hidden="true" tabindex="-1"></a> <span class="fu">union</span><span class="op">(</span>e<span class="op">.</span><span class="fu">s</span><span class="op">,</span>e<span class="op">.</span><span class="fu">d</span><span class="op">);</span></span>
<span id="cb1-62"><a href="#cb1-62" aria-hidden="true" tabindex="-1"></a> cost <span class="op">+=</span> e<span class="op">.</span><span class="fu">cost</span><span class="op">;</span></span>
<span id="cb1-63"><a href="#cb1-63" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-64"><a href="#cb1-64" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-65"><a href="#cb1-65" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> cost<span class="op">;</span></span>
<span id="cb1-66"><a href="#cb1-66" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-67"><a href="#cb1-67" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-68"><a href="#cb1-68" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">void</span> <span class="fu">settings</span><span class="op">(</span><span class="bu">PriorityQueue</span><span class="op"><</span>Edge<span class="op">></span> priorityQueue<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-69"><a href="#cb1-69" aria-hidden="true" tabindex="-1"></a> nodes<span class="op">.</span><span class="fu">sort</span><span class="op">(</span><span class="bu">Comparator</span><span class="op">.</span><span class="fu">comparingInt</span><span class="op">(</span>o <span class="op">-></span> o<span class="op">.</span><span class="fu">x</span><span class="op">));</span></span>
<span id="cb1-70"><a href="#cb1-70" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-71"><a href="#cb1-71" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> n<span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb1-72"><a href="#cb1-72" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>i <span class="op">-</span> <span class="dv">1</span> <span class="op">>=</span> <span class="dv">0</span><span class="op">)</span></span>
<span id="cb1-73"><a href="#cb1-73" aria-hidden="true" tabindex="-1"></a> priorityQueue<span class="op">.</span><span class="fu">add</span><span class="op">(</span></span>
<span id="cb1-74"><a href="#cb1-74" aria-hidden="true" tabindex="-1"></a> <span class="fu">getEdge</span><span class="op">(</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">),</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">-</span><span class="dv">1</span><span class="op">),</span><span class="ch">'x'</span><span class="op">));</span></span>
<span id="cb1-75"><a href="#cb1-75" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>i <span class="op">+</span> <span class="dv">1</span> <span class="op"><</span> n<span class="op">)</span></span>
<span id="cb1-76"><a href="#cb1-76" aria-hidden="true" tabindex="-1"></a> priorityQueue<span class="op">.</span><span class="fu">add</span><span class="op">(</span></span>
<span id="cb1-77"><a href="#cb1-77" aria-hidden="true" tabindex="-1"></a> <span class="fu">getEdge</span><span class="op">(</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">),</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">+</span><span class="dv">1</span><span class="op">),</span><span class="ch">'x'</span><span class="op">));</span></span>
<span id="cb1-78"><a href="#cb1-78" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-79"><a href="#cb1-79" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-80"><a href="#cb1-80" aria-hidden="true" tabindex="-1"></a> nodes<span class="op">.</span><span class="fu">sort</span><span class="op">(</span><span class="bu">Comparator</span><span class="op">.</span><span class="fu">comparingInt</span><span class="op">(</span>o <span class="op">-></span> o<span class="op">.</span><span class="fu">y</span><span class="op">));</span></span>
<span id="cb1-81"><a href="#cb1-81" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-82"><a href="#cb1-82" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> n<span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb1-83"><a href="#cb1-83" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>i <span class="op">-</span> <span class="dv">1</span> <span class="op">>=</span> <span class="dv">0</span><span class="op">)</span></span>
<span id="cb1-84"><a href="#cb1-84" aria-hidden="true" tabindex="-1"></a> priorityQueue<span class="op">.</span><span class="fu">add</span><span class="op">(</span></span>
<span id="cb1-85"><a href="#cb1-85" aria-hidden="true" tabindex="-1"></a> <span class="fu">getEdge</span><span class="op">(</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">),</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">-</span><span class="dv">1</span><span class="op">),</span><span class="ch">'y'</span><span class="op">));</span></span>
<span id="cb1-86"><a href="#cb1-86" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>i <span class="op">+</span> <span class="dv">1</span> <span class="op"><</span> n<span class="op">)</span></span>
<span id="cb1-87"><a href="#cb1-87" aria-hidden="true" tabindex="-1"></a> priorityQueue<span class="op">.</span><span class="fu">add</span><span class="op">(</span></span>
<span id="cb1-88"><a href="#cb1-88" aria-hidden="true" tabindex="-1"></a> <span class="fu">getEdge</span><span class="op">(</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">),</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">+</span><span class="dv">1</span><span class="op">),</span><span class="ch">'y'</span><span class="op">));</span></span>
<span id="cb1-89"><a href="#cb1-89" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-90"><a href="#cb1-90" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-91"><a href="#cb1-91" aria-hidden="true" tabindex="-1"></a> nodes<span class="op">.</span><span class="fu">sort</span><span class="op">(</span><span class="bu">Comparator</span><span class="op">.</span><span class="fu">comparingInt</span><span class="op">(</span>o <span class="op">-></span> o<span class="op">.</span><span class="fu">z</span><span class="op">));</span></span>
<span id="cb1-92"><a href="#cb1-92" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-93"><a href="#cb1-93" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> n<span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb1-94"><a href="#cb1-94" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>i <span class="op">-</span> <span class="dv">1</span> <span class="op">>=</span> <span class="dv">0</span><span class="op">)</span></span>
<span id="cb1-95"><a href="#cb1-95" aria-hidden="true" tabindex="-1"></a> priorityQueue<span class="op">.</span><span class="fu">add</span><span class="op">(</span></span>
<span id="cb1-96"><a href="#cb1-96" aria-hidden="true" tabindex="-1"></a> <span class="fu">getEdge</span><span class="op">(</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">),</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">-</span><span class="dv">1</span><span class="op">),</span><span class="ch">'z'</span><span class="op">));</span></span>
<span id="cb1-97"><a href="#cb1-97" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>i <span class="op">+</span> <span class="dv">1</span> <span class="op"><</span> n<span class="op">)</span></span>
<span id="cb1-98"><a href="#cb1-98" aria-hidden="true" tabindex="-1"></a> priorityQueue<span class="op">.</span><span class="fu">add</span><span class="op">(</span></span>
<span id="cb1-99"><a href="#cb1-99" aria-hidden="true" tabindex="-1"></a> <span class="fu">getEdge</span><span class="op">(</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">),</span>nodes<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">+</span><span class="dv">1</span><span class="op">),</span><span class="ch">'z'</span><span class="op">));</span></span>
<span id="cb1-100"><a href="#cb1-100" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-101"><a href="#cb1-101" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-102"><a href="#cb1-102" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-103"><a href="#cb1-103" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> Edge <span class="fu">getEdge</span><span class="op">(</span><span class="bu">Node</span> n1<span class="op">,</span> <span class="bu">Node</span> n2<span class="op">,</span> <span class="dt">char</span> check<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-104"><a href="#cb1-104" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> res<span class="op">;</span></span>
<span id="cb1-105"><a href="#cb1-105" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-106"><a href="#cb1-106" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>check <span class="op">==</span> <span class="ch">'x'</span><span class="op">)</span></span>
<span id="cb1-107"><a href="#cb1-107" aria-hidden="true" tabindex="-1"></a> res <span class="op">=</span> <span class="bu">Math</span><span class="op">.</span><span class="fu">abs</span><span class="op">(</span>n1<span class="op">.</span><span class="fu">x</span> <span class="op">-</span> n2<span class="op">.</span><span class="fu">x</span><span class="op">);</span></span>
<span id="cb1-108"><a href="#cb1-108" aria-hidden="true" tabindex="-1"></a> <span class="cf">else</span> <span class="cf">if</span> <span class="op">(</span>check <span class="op">==</span> <span class="ch">'y'</span><span class="op">)</span></span>
<span id="cb1-109"><a href="#cb1-109" aria-hidden="true" tabindex="-1"></a> res <span class="op">=</span> <span class="bu">Math</span><span class="op">.</span><span class="fu">abs</span><span class="op">(</span>n1<span class="op">.</span><span class="fu">y</span> <span class="op">-</span> n2<span class="op">.</span><span class="fu">y</span><span class="op">);</span></span>
<span id="cb1-110"><a href="#cb1-110" aria-hidden="true" tabindex="-1"></a> <span class="cf">else</span></span>
<span id="cb1-111"><a href="#cb1-111" aria-hidden="true" tabindex="-1"></a> res <span class="op">=</span> <span class="bu">Math</span><span class="op">.</span><span class="fu">abs</span><span class="op">(</span>n1<span class="op">.</span><span class="fu">z</span> <span class="op">-</span> n2<span class="op">.</span><span class="fu">z</span><span class="op">);</span></span>
<span id="cb1-112"><a href="#cb1-112" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-113"><a href="#cb1-113" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="kw">new</span> <span class="fu">Edge</span><span class="op">(</span>n1<span class="op">.</span><span class="fu">idx</span><span class="op">,</span>n2<span class="op">.</span><span class="fu">idx</span><span class="op">,</span>res<span class="op">);</span></span>
<span id="cb1-114"><a href="#cb1-114" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-115"><a href="#cb1-115" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-116"><a href="#cb1-116" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span> <span class="fu">find</span><span class="op">(</span><span class="dt">int</span> t<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-117"><a href="#cb1-117" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>parent<span class="op">[</span>t<span class="op">]</span> <span class="op">!=</span> t<span class="op">)</span></span>
<span id="cb1-118"><a href="#cb1-118" aria-hidden="true" tabindex="-1"></a> parent<span class="op">[</span>t<span class="op">]</span> <span class="op">=</span> <span class="fu">find</span><span class="op">(</span>parent<span class="op">[</span>t<span class="op">]);</span></span>
<span id="cb1-119"><a href="#cb1-119" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> parent<span class="op">[</span>t<span class="op">];</span></span>
<span id="cb1-120"><a href="#cb1-120" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-121"><a href="#cb1-121" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-122"><a href="#cb1-122" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">void</span> <span class="fu">union</span><span class="op">(</span><span class="dt">int</span> x<span class="op">,</span> <span class="dt">int</span> y<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-123"><a href="#cb1-123" aria-hidden="true" tabindex="-1"></a> x <span class="op">=</span> <span class="fu">find</span><span class="op">(</span>x<span class="op">);</span></span>
<span id="cb1-124"><a href="#cb1-124" aria-hidden="true" tabindex="-1"></a> y <span class="op">=</span> <span class="fu">find</span><span class="op">(</span>y<span class="op">);</span></span>
<span id="cb1-125"><a href="#cb1-125" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-126"><a href="#cb1-126" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>x <span class="op">!=</span> y<span class="op">)</span></span>
<span id="cb1-127"><a href="#cb1-127" aria-hidden="true" tabindex="-1"></a> parent<span class="op">[</span>x<span class="op">]</span> <span class="op">=</span> y<span class="op">;</span></span>
<span id="cb1-128"><a href="#cb1-128" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-129"><a href="#cb1-129" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
</div>
</body>
</html>