[백준/JAVA] 1197번: 최소 스패닝 트리

🔺 문제

1197번: 최소 스패닝 트리

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static PriorityQueue<pEdge> pq;  // 에지 리스트 - 자동 정렬 위해 우선순위 큐 사용
    static int[] 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());   // 간선
        
        // 유니온 파인드 배열 초기화
        parent = new int[V + 1];
        for(int i = 1 ; i <= V ; i++) {
            parent[i] = i;
        }
        
        // 에지 리스트 채우기
        pq = new PriorityQueue<>();
        for(int i = 1 ; i <= E ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int s  = Integer.parseInt(st.nextToken()); 
            int e    = Integer.parseInt(st.nextToken()); 
            int v = Integer.parseInt(st.nextToken());
            
            pq.add(new pEdge(s, e, v));
        }
      
        // 사이클 발생 여부 판단
        int useEdge = 0;
        int result = 0;
        while(useEdge < V - 1) {
            pEdge now = pq.poll();
 
            if(find(now.s) != find(now.e)) {
                union(now.s, now.e);
                result += now.v;    // 에지 가중치를 정답 변수에 더하기
                useEdge++;
            }
        }
        System.out.println(result);
    }
    
    // 유니온파인드
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
    public static int find(int a) {
        if(a == parent[a]) return a;
        else             return parent[a] = find(parent[a]);
    }
}
// 간선 정보 저장용
class pEdge implements Comparable<pEdge> {
    int s, e, v;
    
    pEdge(int s, int e, int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
    
    @Override
    public int compareTo(pEdge e) {
        return this.v - e.v;
    }
}

✅ 해결 아이디어
✔ 최소 신장 트리 (크루스칼 알고리즘 - 유니온 파인드)

 

💥 유의사항

• 그래프 사이클 형성 여부 판단 방법 :  노드1 값 ≠ 노드2 값 일 때 사이클이 없는 것이므로, 이 때 union 연산 수행

• 에지 리스트, 자동 정렬 위해 Priority Queue 사용!

 

---

🔺 다른 풀이들

- 크루스칼 알고리즘을 사용하셨다. & 우선순위 큐 사용 안 하심

[백준] 1197 - 최소 스패닝 트리 (java)

백준 1197번 : 최소 스패닝 트리 java

 

 

- 프림 알고리즘을 사용하셨다.

[Algorithm/Java][백준] 1197번 최소 스패닝 트리

 

 

- 설명이 깔끔 & 굿

[JAVA]백준 1197번: 최소 스패닝 트리

[백준 1197] 최소 스패닝 트리 (자바)

---

💬 느낀 점

앞에서 하던 거랑 크게 다른 느낌은 아님....

그냥 조건만 좀 다른 것 같다고 느낌...

 

 

1회독	2회독	3회독	4회독	5회독
V	5/22	6/27

 

 

(+ 6/27 3회독)

코드 거의 비슷...

import java.util.*;
import java.io.*;
 
public class Main {
    static int V, E;
    static PriorityQueue<Edge> edges;   // 🔔 그래프 에지 리스트 🔔
    static int[] parent;                // 유니온파인드용 대표 노드 배열
    static int useEdge = 0;             // 에지 개수
    static int result = 0;              // 결과
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        // 변수들 초기화
        edges = new PriorityQueue<>();
        parent = new int[V + 1];
        for(int i = 1 ; i <= V ; i++) {
            parent[i] = i;
        }
        
        // 입력 받기
        while(E --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            edges.add(new Edge(a, b, c));
        }
        
        // 🔔 최소 신장 트리 (MST) 수행 🔔
        while(useEdge < V - 1) {
            Edge now = edges.poll();
            
            if(find(now.s) != find(now.e)) {
                union(now.s, now.e);
                result += now.v;
                useEdge++;
            }
        }
        System.out.println(result);
    }
    
    // 유니온파인드
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b)  parent[b] = a;
    }
    static int find(int a) {
        if(a == parent[a])  return a;
        return parent[a] = find(parent[a]);
    }
}
 
class Edge implements Comparable<Edge> {
    int s, e, v;
    
    public Edge(int s, int e, int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
    
    // 오름차순 정렬
    @Override
    public int compareTo(Edge edge) {
        return this.v - edge.v;
    }
}
 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편