Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 네트워크플로우
- QUICKSTARTGUIDE
- 자바PS
- 다익스트라
- 이젠 골드구현도 어렵네..
- spring
- dp
- deque
- 엘라스틱서치
- GatherTown
- 알고리즘
- 완전탐색
- 세그먼트트리
- PS
- BFS
- DFS
- 구현
- 게더타운시작
- 백준코딩테스트
- 시뮬레이션
- java
- 우선순위큐
- 재귀함수
- 01BFS
- COSPROJAVA1급
- YBMCOS
- 백준
- COSPRO
- 취득후기
- 다이나믹프로그래밍
Archives
- Today
- Total
공부공간
BOJ - 1647 ) 도시분할계획 본문
https://www.acmicpc.net/problem/1647
최소 컴포넌트의 크기가 2개가 되야 하므로, 초기 N개의 컴포넌트에서
Kruskal 알고리즘으로 성공적으로 Union되었을시, 컴포넌트의 개수를 감소시킨다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class 도시분할계획 {
public static class node{
int s , e ,c ;
public node(int s, int e, int c) {
super();
this.s = s;
this.e = e;
this.c = c;
}
}
public static int [] parent;
public static void main(String[] args) throws Exception {
// kruskal algorithm
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
PriorityQueue<node> pq= new PriorityQueue<>(new Comparator<node>() {
@Override
public int compare(node o1, node o2) {
if(o1.c > o2.c) {
return 1;
} else if(o1.c == o2.c) {
return 0;
} else {
return -1;
}
}
});
for(int i = 0 ; i < k ; i++) {
st = new StringTokenizer(br.readLine());
int s,e,c;
s = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
pq.add(new node(s-1, e-1, c));
}
parent= new int[n];
int answer =0;
make();
// union이 성공적으로 된다면 , n--해준다.
while(n > 2) {
node now = pq.poll();
if(union(now.s , now.e)) {
n--;
answer += now.c;
}
} System.out.println(answer);
}
private static boolean union(int ps, int pe) {
ps = findp(ps);
pe = findp(pe);
if(ps==pe) return false;
if(ps > pe) {
parent[ps] = pe;
} else {
parent[pe] = ps;
}
// 항상 ps가 작다.
return true;
}
private static void make() {
for(int i = 0 ; i < parent.length ; i++) {
parent[i] = i;
}
}
private static int findp (int x) {
if(parent[x] ==x ) return x;
else { return findp(parent[x]);}
}
}
'알고리즘 > 구현,시뮬' 카테고리의 다른 글
BOJ - 2887 ) 행성 터널 (0) | 2020.07.07 |
---|---|
BOJ - 6497 ) 전력난 (0) | 2020.07.07 |
BOJ - 2230 ) 수 고르기 (0) | 2020.06.29 |
BOJ - 1806 ) 부분합 (0) | 2020.05.11 |
BOJ - 1644 ) 소수의 연속합 (0) | 2020.05.11 |
Comments