1197 자바 - 최소 신장 트리

Kruskal

 

자바에서 배열을 정렬할 땐 Arrays.sort()를 사용한다.

오름차순으로 정렬하고 싶다면 그냥 Arrays.sort(배열이름) 이렇게 해주면 되고,

이번 문제 처럼 배열의 두 번째 원소로 정렬을 하고 싶다면 아래와 같이 람다 표현식을 같이 써주어야 한다. 

Arrays.sort(graph, (o1,o2)->(o1[2]-o2[2]));

-> 배열 o1, o2를 비교할 때 세 번째 열 값을 기준으로 오름차순으로 정렬하겠다는 뜻

 

원리는 바로 앞선 포스트인 https://marc11.tistory.com/147와 같아서 코드만 첨부하겠다~~

import java.io.*;
import java.util.*;


public class Main {

    public static int find(int x,int[] parent){
        if (parent[x]==x)
            return parent[x];
        return find(parent[x],parent);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int V=Integer.parseInt(st.nextToken());
        int E=Integer.parseInt(st.nextToken());

        int[][] graph= new int[E][3];
        int[] parent = new int[V+1];

        for(int i=0;i<E;i++){
            st=new StringTokenizer(br.readLine());
            graph[i][0]=Integer.parseInt(st.nextToken());
            graph[i][1]=Integer.parseInt(st.nextToken());
            graph[i][2]=Integer.parseInt(st.nextToken());
        }
        for(int i=0;i<V+1;i++){
            parent[i]=i;
        }

        Arrays.sort(graph, (o1,o2)->(o1[2]-o2[2]));

        int cnt=0;
        for(int i=0;i<E;i++){
            int p0=find(graph[i][0],parent);
            int p1=find(graph[i][1],parent);
            if (p0!=p1){
                if (p0>p1){
                    parent[p0]=p1;
                }
                else if (p0<p1){
                        parent[p1]=p0;
                }
                cnt+=graph[i][2];
            }
        }
        System.out.println(cnt);
    }

}

 

---

Prim

 

ArrayList에 리스트를 add 하려면 단순히 ar.add([]) 형태가 아니다!

간선을 저장하기 위한 클래스를 따로 만들어 주고 객체를 넣어주어여 한다!!

class Edge implements Comparable<Edge>{
	int w; // 간선 들어오는 정점
	int cost; // 간선 가중치
	
	Edge(int  w, int cost){
		this.w = w;
		this.cost = cost;
	}
	
    // 간선 오름차순으로 정렬
	@Override
	public int compareTo(Edge o) {
		return this.cost - o.cost;
	}
}

-> compareTo() 메소드를 이용하여 Edge 객체들을 cost를 기준으로 오름차순 정렬을 해주기 위해 Comparable<Edge> 를 구현함!!

-> 기존 compareTo() 메소드를 재정의 해주었기에 Override

---

자바에서는 Priority Queue를 이용하여 최소힙, 최대힙을 구현할 수 있다.

Integer가 아닌 다른 값을 비교하여 최소힙을 만드는 경우, Comparable을 구현하여 생성한 클래스를 이용하고 이 객체를 힙에 add 한다.

 

Priority Queue 

1. 데이터 추가

  : add / offer

2. 데이터 삭제+반환

  : poll (pop과 같은 역할)

 

import java.io.*;
import java.util.*;



public class Main {

    static class Edge implements Comparable<Edge>{
        int cost;
        int c;
        public Edge(int cost, int c){
            this.cost=cost;
            this.c=c;
        }

        @Override
        public int compareTo(Edge e){
            return this.cost-e.cost;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < V + 1; i++) {
            graph.add(new ArrayList<>());
        }
        boolean[] visited = new boolean[V + 1];

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Edge(c, b));
            graph.get(b).add(new Edge(c, a));
        }
        for (int i = 0; i < V + 1; i++) {
            visited[i] = false;
        }

        PriorityQueue<Edge> minHeap= new PriorityQueue<>();
        minHeap.add(new Edge(0,1));
        int mst=0;
        while (!minHeap.isEmpty()){
            Edge temp=minHeap.poll();
            int cost=temp.cost;
            int c=temp.c;
            if(!visited[c]){
                mst+=cost;
                visited[c]=true;
                for(Edge g:graph.get(c)){
                    if(!visited[g.c]){
                        minHeap.add(g);
                    }
                }
            }
        }
        System.out.print(mst);

    }

}

 

실행결과 Kruskal보다 Prim이 0.1초 정도 빨랐다