깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.
이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.
만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다.
이때, 주어지는 거리 데이터를 이용하여 사심 경로의 길이를 구해보자.
입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000)
둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다.
다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000)
깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.)
int u, v, d;
for (int i = 0; i < M; i++) {
in = br.readLine().split(" ");
u = Integer.parseInt(in[0]);
v = Integer.parseInt(in[1]);
d = Integer.parseInt(in[2]);
// 동일한 성별이면 리스트에서 제외한다
if (arr[u] == arr[v]) continue;
edgeList.add(new Edge(u, v, d));
}
Collections.sort(edgeList, (o1, o2) -> Integer.compare(o1.d, o2.d));
initParents();
int nodeCnt = 0;
int answer = 0;
for (Edge temp : edgeList) {
if (union(temp.u, temp.v)) {
nodeCnt++;
answer += temp.d;
if (nodeCnt == N - 1) {
System.out.println(answer);
return;
}
}
}
System.out.println(-1);
package BOJ;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BOJ_나만안되는연애_HoonyCode {
static int N, M;
static char[] arr;
static int[] parents;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 학교의 수 N 과 도로의 개수 M;
String[] in = br.readLine().split(" ");
N = Integer.parseInt(in[0]);
M = Integer.parseInt(in[1]);
parents = new int[N + 1];
arr = new char[N + 1];
in = br.readLine().split(" ");
// 남 녀 구별 M // W;
for (int i = 1; i <= N; i++) {
arr[i] = in[i - 1].charAt(0);
}
List<Edge> edgeList = new ArrayList<>();
int u, v, d;
for (int i = 0; i < M; i++) {
in = br.readLine().split(" ");
u = Integer.parseInt(in[0]);
v = Integer.parseInt(in[1]);
d = Integer.parseInt(in[2]);
if (arr[u] == arr[v]) continue;
edgeList.add(new Edge(u, v, d));
}
Collections.sort(edgeList, (o1, o2) -> Integer.compare(o1.d, o2.d));
initParents();
int nodeCnt = 0;
int answer = 0;
for (Edge temp : edgeList) {
if (union(temp.u, temp.v)) {
nodeCnt++;
answer += temp.d;
if (nodeCnt == N - 1) {
System.out.println(answer);
return;
}
}
}
System.out.println(-1);
}
static boolean union(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
} else {
parents[y] = x;
return true;
}
}
static void initParents() {
for (int i = 1; i <= N; i++) {
parents[i] = i;
}
}
static int find(int x) {
if (x != parents[x]) {
return parents[x] = find(parents[x]);
}
return parents[x];
}
static class Edge {
int u, v, d;
public Edge(int u, int v, int d) {
this.u = u;
this.v = v;
this.d = d;
}
}
}