[백준] 1647 : 도시 분할 계획 (JAVA/자바)

흶·2021년 7월 21일

MST boj 알고리즘 우선순위큐 프림

Algorithm

목록 보기

23/60

문제

BOJ 1647 : 도시 분할 계획 - https://www.acmicpc.net/problem/1647

풀이

문제를 이해하기가 좀 어려웠는데, 가장 적은 비용으로 두 마을로 나누는 문제이다.

MST(최소 스패닝 트리)를 구한 후 가장 큰 가중치의 간선을 제외하면 가장 적은 비용으로 마을을 두개로 나눌 수 있다!

MST를 구하는 방법으로는 대표적으로 Kruskal Algorithm과 Prim Algorithm이 있다. Kruskal은 상대적으로 잘 알고있다고 느껴져서 이번 문제에서는 프림 알고리즘으로 풀이해보았다.

[Prim Algorithm]

위 예제를 간단하게 이해해보자.

1. 시작점(a)을 정한 뒤, 그 점으로부터 연결되어있는 간선 중에 가중치가 가장 작은 간선을 선택한다. 그 간선에 의해 연결되어있는 점(b)이 그래프에 포함된다.

2. 점(a),(b)로부터 연결되어있는 간선 중에 가중치가 가장 작은 간선을 선택한다. (8, 11, 8이기 때문에 8의 가중치를 가지는 간선 중 아무거나 선택하면 된다.)

3. 선택된 간선에 의해 점(c)도 그래프에 포함된다.

2-1. 점(a),(b),(c)로부터 연결되어있는 간선 중에 가중치가 가장 작은 간선을 선택한다.

3-1. 선택된 간선에 의해 점(i)도 그래프에 포함된다.

...(반복)...

4. 모든 점이 선택되면 (그래프를 이루는 점의 수가 N이면) 종료한다.

가장 작은 간선을 구하는 효율적인 코드를 작성하기 위해 Priority Queue를 사용했다. (Priority Queue의 삭제(poll) 시간복잡도는 O(1)이다.) 가장 작은 간선이 큐의 가장 앞에 위치하기 때문에 단순히 poll()을 호출하면 가장 작은 간선을 얻을 수 있다.

코드

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

public class Main {

    static class Node implements Comparable<Node>{
        int idx;
        int weight;

        public Node(int idx, int weight) {
            this.idx = idx;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node e) {
            return this.weight - e.weight;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int N = Integer.parseInt(inputs[0]);
        int M = Integer.parseInt(inputs[1]);

        ArrayList<Node>[] nodes = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            nodes[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++){
            inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            int w = Integer.parseInt(inputs[2]);

            nodes[a].add(new Node(b, w));
            nodes[b].add(new Node(a, w));
        }
        
        boolean visited[] = new boolean[N+1]; // 해당 노드가 선택되었는지 아닌지 판단

        int cnt = 0; 		// 선택된 노드 수 카운트
        int result = 0; 	// MST를 이루는 간선의 총합
        int max_weight = 0; 	// MST중 가장 큰 weight

        PriorityQueue<Node> q = new PriorityQueue<Node>();

        q.add(new Node(1, 0));

        while (true) {
            Node cur = q.poll(); // extract min

            if (visited[cur.idx]) continue; // 이미 방문했었으면 패스

            visited[cur.idx] = true;
            result += cur.weight;
            max_weight = Math.max(max_weight, cur.weight);
            cnt++;

            if (cnt == N) break;

            for (Node v : nodes[cur.idx]) {
                if (!visited[v.idx]) {
                    q.add(new Node(v.idx, v.weight));
                }
            }
        }
        
        System.out.println(result-max_weight);
    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 최소 스패닝 트리
✔ 난이도 - 🟡 Gold 4

🤦‍♀️ 오늘의 메모

Extract-Min을 할때는 Priority Queue를 사용한다는 것 기억하기.
Priority Queue의 우선순위 기준을 정하는 방법은 여러가지가 있다.

기본

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); // 오름차순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순

별도로 생성하는 class에 Comparable을 implements하고, compareTo()를 override한다.

static class Node implements Comparable<Node>{
        int idx;
        int weight;

        ...

        @Override
        public int compareTo(Node e) {
            return this.weight - e.weight;
        }
        // '[this(자기 자신)]-[other]' 형태
        // 음수 : 오름차순으로 만들고 싶을 때. (this(1)-other(5)인 경우 -4 반환, 앞이 더 작다는 의미)
        // 0 : 두 개의 원소가 같은 경우
        // 양수 : 내림차순으로 만들고 싶을 때. (this(5)-other(1)인 경우 4 반환, 앞이 더 크다는 의미)
}

...

PriorityQueue<Node> q = new PriorityQueue<Node>();

Comparator객체 생성 (특정 기준으로 정렬하고 싶을 때)
예) 문자열 중 2번째 자리로 정렬

PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<String>() {

    @Override
    public int compare(String o1, String o2) {
        if(o1.charAt(1) < o2.charAt(1)) {
            return -1;
        }else if(o1.charAt(1) > o2.charAt(1)) {
            return 1;
        }else {
            return 0;
        }
        
        /*
        return o1.compareTo(o2);            //전체 오름 차순
        return o2.compareTo(o1);            //전체 내림차순
        */
    }
});