[BOJ] 1197. 최소 스패닝 트리

MST 문제이다. 이 문제를 풀기 위해선 Kruskal 이나 Prim을 사용해야한다. 참고

이 문제를 두가지방법 모두 사용하여 풀어보았다. 첫번째로 Kruskal 알고리즘을 사용하였는데 , 정렬을 함에 있어 PriorityQueue를 사용하였고, 같은 팀임을 보기 위해 UnionFind를 같이 사용하였다. 

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_1197_최소스패닝트리_re {
    
    static int[] parents;
    
    static int V,E;
    
    static PriorityQueue<Edge> pq;
    static int result=0;
    
    static class Edge implements Comparable<Edge>{
        int v1,v2,w;
        public Edge(int v1,int v2, int w) {
            this.v1=v1;this.v2=v2;this.w=w;
        }
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(w, o.w);
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V=Integer.parseInt(st.nextToken());
        E=Integer.parseInt(st.nextToken());
        
        pq=new PriorityQueue<>();
        for(int i=0;i<E;i++) {
            st=new StringTokenizer(br.readLine());
            int v1= Integer.parseInt(st.nextToken())-1;
            int v2= Integer.parseInt(st.nextToken())-1;
            int w= Integer.parseInt(st.nextToken());
            
            pq.offer(new Edge(v1, v2, w));
        }
        kruskal();
        System.out.println(result);
    }
    
    static void kruskal() {
        parents=new int[V];
        for(int i=0;i<V;i++)
            parents[i]=i;        //makeSet;
        
        int cnt=0;
        for(int i=0;i<E;i++) {
            int a=findSet(pq.peek().v1);
            int b=findSet(pq.peek().v2);
            
            if(a==b) {    //부모가 같으면 패스
                pq.poll();
                continue;
            }
            
            union(a, b);
            
            result+=pq.peek().w;
            pq.poll();
            
            cnt++;
            if(cnt==V-1)
                break;
        }
    }
    
    static int findSet(int x) {
        if(x==parents[x])
            return x;
            
        parents[x]=findSet(parents[x]);
        return parents[x];
    }
    
    static void union(int x,int y) {
        int px = findSet(x);
        int py = findSet(y);
        
        if(px<py)
            parents[py]=px;
        else
            parents[px]=py;
            
    }
    
}
 

 

두번째 방법으로는 Prim을 사용하였다. Prim은 정점이 기준이기에 이차원 행렬을 사용하려고 하였지만 이차원행렬의 크기에서 메모리초과오류가 발생하여, 인접리스트를 사용하여 구현하였다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_1197_최소스패닝트리 {
    //Prim 사용한 MST
    
    static int V,E;
    static ArrayList<Pos>[] adj;
    
    static boolean[] check;    //방문
    static int[] key;    //현재 선택된 정점들로부터 도달할 수 있는 최소 거리
    static int[] p;    //최소신장트리의 구조 저장
    
    static class Pos{
        int v2,w;
        public Pos(int v2,int w) {
            this.v2=v2; this.w=w;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        V=Integer.parseInt(st.nextToken());
        E=Integer.parseInt(st.nextToken());
 
        //인접리스트를 이용
        adj=new ArrayList[V];
        for(int i=0;i<V;i++) {
            adj[i]=new ArrayList<Pos>();
        }
        
        for(int i=0;i<E;i++) {
            st=new StringTokenizer(br.readLine());
            int v1= Integer.parseInt(st.nextToken())-1;
            int v2= Integer.parseInt(st.nextToken())-1;
            int w= Integer.parseInt(st.nextToken());
            
            adj[v1].add(new Pos(v2, w));
            adj[v2].add(new Pos(v1, w));
        }
        
        check=new boolean[V];    //방문여부확인
        p=new int[V];            //최소신장트리의 구조 저장, 부모를 저장
        key=new int[V];            //현재 선택된 정점들로부터 도달할수 있는 최소거리
        for(int i=0;i<V;i++) {
            key[i]=Integer.MAX_VALUE;
        }
        
        prim(0);    //임의의 점부터시작, 0부터 시작
        
        int result=0;
        for(int i=0;i<V;i++) {
            result+=key[i];
        }
        System.out.println(result);
    }
    
    static void prim(int start) {
        p[start]=-1;
        key[start]=0;
        
        
        
        //이미하나 골랐기에 나머지 V-1개 고르기
        for(int i=0;i<V-1;i++) {
            int min=Integer.MAX_VALUE;
            int index=-1;
            
            //안골라진지 검사, key의 최소값을 기억
            for(int j=0;j<V;j++) {
                if(check[j]==false && key[j]<min) {
                    index=j; min=key[j];
                }
            }
            
            check[index]=true;
            
            //index정점에서 출발하는 모든 간선에 대해 key업데이트
            for(int j=0;j<adj[index].size();j++) {
                int temp = adj[index].get(j).v2;
                //방문이 안되어있고, index에서 방문이 가능하고, 그 간선이 key값보다 작으면 업데이트
                if(check[temp]==false && adj[index].get(j).w != 0 
                        && key[temp]>adj[index].get(j).w ) {
                    p[temp]=index;
                    key[temp]=adj[index].get(j).w;
                }
            }
        }
    
    }
}
 

세번째로는 Prim알고리즘을 PrioirityQueue와 함께 구현해보았다.

 

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_1197_최소스패닝트리_re3 {
    static int V;
    static int E;
    
    static List<Edge>[] map;
    static boolean[] visit;
    static int[] d;
    
    static int[] way;
    
    
    static class Edge implements Comparable<Edge>{
        int point,weight;
        
        Edge(int p, int w){
            point=p;weight=w;
        }
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(weight, o.weight);
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st=new StringTokenizer(br.readLine());
        V=Integer.parseInt(st.nextToken());
        E=Integer.parseInt(st.nextToken());
 
        visit=new boolean[V];
        d=new int[V];
        way=new int[V];
        for(int i=0;i<V;i++) {    //거리 초기화
            d[i]=Integer.MAX_VALUE;
        }
        
        //map생성
        map=new ArrayList[V];
        for(int i=0;i<V;i++) {
            map[i]=new ArrayList<>();
        }
        
        for(int i=0;i<E;i++) {
            st=new StringTokenizer(br.readLine());
            int start=Integer.parseInt(st.nextToken())-1;
            int dest=Integer.parseInt(st.nextToken())-1;
            int w= Integer.parseInt(st.nextToken());
            
            map[start].add(new Edge(dest, w));
            map[dest].add(new Edge(start, w));
        }
 
        int begin=0;
        
        prim(0);
        
        int dis=0;
        for(int i=0;i<V;i++) {
//            System.out.println(d[i]);
            dis+=d[i];
            System.out.println(way[i]);
        }
        System.out.println(dis);
        
    }
    
    static void prim(int begin) {
        PriorityQueue<Edge> pq= new PriorityQueue<>();
        
        d[begin]=0;
        way[begin]=-1;
        pq.offer(new Edge(begin, 0));
        int cnt=0;
        while(!pq.isEmpty()) {
            Edge e=pq.poll();
            int start=e.point;
            
            if(visit[start]==true)
                continue;
            cnt++;
            for(Edge n : map[start]) {
                int dest= n.point;
                int weight=n.weight;
                
                if(visit[dest]==false && d[dest] > weight) {
                    d[dest]=weight;
//                    way[dest]=start;
                    pq.add(new Edge(dest, weight));
                }
            }
            
            visit[start]=true;
            if(cnt==V-1)
                break;
        }
    }
}