티스토리 뷰

PS/Problem_Solving

[SWEA] 1251.하나로(MST, kruskal, prim).java

Aaron 2020. 9. 23. 00:10
반응형


#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE

* The copyright in this matter is in BOJ


#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it


#. Solve


결국 모든 섬들을 잇는 것이 문제이므로 MST(Minimum Spanning Tree)로 해결해야 한다.


문제에서는 각 섬들을 잇는 가중치의 환경 부담금이 입력으로 주어지지 않고,

직접 계산을 해야한다..


섬들의 X좌표, Y좌표를 입력받고,

모든 간선의 비용을 저장한다.


그 이후 MST 알고리즘

Kruskal 또는 Prim 을 적용해보자.


#. Code_kruskal


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
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static int N, parents[];
    public static double E;
    public static Point[] land;
    public static ArrayList<Edge> edgeList;
    public static class Edge implements Comparable<Edge> {
        int from, to;
        long w;
 
        public Edge(int from, int to, long w) {
            super();
            this.from = from;
            this.to = to;
            this.w = w;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Long.compare(this.w, o.w);
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            
            // 섬의 갯수
            N = Integer.parseInt(br.readLine());
            land = new Point[N];
            parents = new int[N];
            // 섬들의 x 좌표 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) { 
                land[i] = new Point(0, 0);
                land[i].x = Integer.parseInt(st.nextToken());
            }
            // 섬들의 y좌표 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) 
                land[i].y = Integer.parseInt(st.nextToken());
            // 세율
            E = Double.parseDouble(br.readLine());
            
            // 모든 간선의 비용을 저장
            edgeList = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    long distX = Math.abs(land[i].x - land[j].x);
                    long distY = Math.abs(land[i].y - land[j].y); 
                    edgeList.add(new Edge(i, j, distX * distX + distY * distY));
                }
            }
            // 간선 기준 오름차순 정렬
            edgeList.sort(null);
            // 정점 초기화
            make();
            // 가중치가 낮은 간선부터 선택하면서 트리에 추가
            int cnt = 0;
            long res = 0;
            for (Edge edge : edgeList) {
                // 싸이클이 형성되지 않으면
                if(union(edge.from, edge.to)) {
                    // 간선 사용
                    res += edge.w;
                    if(++cnt == N - 1) break;
                }
            }
            // 총 환경 부담금을 최소로 지불하며, N개의 모든 섬을 연결할 수 있는 교통 시스템을 설계
            System.out.println("#" + tc + " " + Math.round(res * E));
        }
    }
 
    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        // 사이클이 형성되면
        if(aRoot == bRoot) return false;
        parents[bRoot] = aRoot;
        return true;
    }
 
    private static int find(int a) {
        if(a == parents[a]) return a;
        return parents[a] = find(parents[a]);
    }
 
    private static void make() {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }    
    
}
 
cs



#. Code_prim


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
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static class Node implements Comparable<Node> {
        int no;
        long w;
 
        public Node(int no, long w) {
            this.no = no;
            this.w = w;
        }
 
        @Override
        public int compareTo(Node o) {
            return Long.compare(this.w, o.w);
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            
            // 섬의 갯수
            int N = Integer.parseInt(br.readLine());
            Point[] land = new Point[N];
            boolean[] visited = new boolean[N];
            // 섬들의 x 좌표 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) { 
                land[i] = new Point(0, 0);
                land[i].x = Integer.parseInt(st.nextToken());
            }
            // 섬들의 y좌표 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) 
                land[i].y = Integer.parseInt(st.nextToken());
            // 세율
            double E = Double.parseDouble(br.readLine());
            
            // 모든 간선의 비용을 저장
            ArrayList<Node>[] adj = new ArrayList[N];
            for (int i = 0; i < N; i++) {
                adj[i] = new ArrayList<>();
                
                for (int j = 0; j < N; j++) {
                    if(i == j) continue;
                    long distX = Math.abs(land[i].x - land[j].x);
                    long distY = Math.abs(land[i].y - land[j].y); 
                    adj[i].add(new Node(j, distX * distX + distY * distY));
                }
                
            }
            
            long res = 0;
            int nodeCnt = 0;
            PriorityQueue<Node> q = new PriorityQueue<>();
            q.add(new Node(0, 0));
        
            while(!q.isEmpty()) {
                Node now = q.poll();
                // 이미 확인한 노드는 pass
                if(visited[now.no]) continue;
                
                res += now.w;
                visited[now.no] = true;
                // 모든 노드 확인 완료
                if(++nodeCnt == N) break;
                
                for (int i = 0; i < adj[now.no].size(); i++) {
                    Node next = adj[now.no].get(i);
                    if(!visited[next.no]) {
                        q.add(next);
                    }
                }
            }
            
            // 총 환경 부담금을 최소로 지불하며, N개의 모든 섬을 연결할 수 있는 교통 시스템을 설계
            System.out.println("#" + tc + " " + Math.round(res * E));
        }
    }
}
 
cs



반응형
저작자표시

'PS > Problem_Solving' 카테고리의 다른 글

[BOJ] 1149.RGB거리(DP).java  (0) 2020.09.23
[BOJ] 11048.이동하기(DP).java  (0) 2020.09.23
[SWEA] 3282. 0/1 Knapsack(DP).java  (0) 2020.09.22
[BOJ] 4179.불(BFS).java  (2) 2020.09.16
[BOJ]17780.새로운 게임(시뮬레이션).java  (0) 2020.09.15
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday
TAG more