[백준 알고리즘] 10423번: 전기가 부족해 (JAVA)

https://www.acmicpc.net/problem/10423

10423번: 전기가 부족해

 

---

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

static int N,M,K,ans;
    static boolean[] visited;
    static ArrayList<ArrayList<Node>> graph;
    static ArrayList<Integer> elec;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

         N = Integer.parseInt(st.nextToken());
         M = Integer.parseInt(st.nextToken());
         K = Integer.parseInt(st.nextToken());

         elec = new ArrayList<Integer>();
         visited = new boolean[N+1];
         graph = new ArrayList<ArrayList<Node>>();

         for (int i=0; i<=N; i++) {
            graph.add(new ArrayList<>());
         }

         st = new StringTokenizer(br.readLine());
         for (int i=0; i<K; i++) {
            elec.add(Integer.parseInt(st.nextToken())); 
         }

         for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.get(u).add(new Node(v,w));
            graph.get(v).add(new Node(u,w));
         }

         Prim();
         System.out.println(ans);
    
    }

    public static void Prim() {
        PriorityQueue<Node> pq = new PriorityQueue<Node>();

        ans = 0;

        for (int i=0; i<elec.size(); i++) { // 발전소가 있는 위치를 우선순위 큐에 한번에 넣어줌
            pq.offer(new Node(elec.get(i),0));
        }

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (visited[cur.x]) continue;

            visited[cur.x] = true;
            ans += cur.weight;

            for (Node next: graph.get(cur.x)) {
                if (!visited[next.x] && check(next.x)) {
                    pq.offer(new Node(next.x, next.weight));
                }
            }
        }
    }

    public static boolean check(int x) {
        if (elec.contains(x)) return false;
        return true;
    }
}

class Node implements Comparable<Node>{
    int x;
    int weight;
    public Node(int x, int weight) {
        this.x = x;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

 

 

---

풀이

★ 문제 유형은 최소 신장 트리이고, 간선의 수가 정점의 수보다 많기 때문에 저는 "프림" 알고리즘을 사용해 문제를 해결하였습니다.

 

★ 전체적인 틀은 프림 알고리즘의 기본 구조와 크게 다르지 않습니다. 전 두가지를 고려해줬습니다.

 

1. 발전소의 위치를 한번에 우선순위 큐에 넣은 뒤, prim 알고리즘을 수행한다.

2. 발전소가 있는 정점이면 따로 방문하지 않는다.

 

사실 1번은 이전에 비슷한 유형의 문제를 풀어본 경험이 없다면 아이디어가 쉽게 떠오르지 않았을 거라고 생각하기도 했습니다 ! (하지만 정답률이 꽤 높군요 ㅎㅎ)