[백준]1647: 도시 분할 계획 - JAVA

[백준]1647: 도시 분할 계획

 

 

www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

풀이

집이 모두 연결되어 있는 상태에서 연결된 집을 두개의 마을로 나누는 문제이다. MST알고리즘을 사용하여 풀면 된다.

MST알고리즘은 최소 간선을 선택해서 모든 노드를 연결한 경로를 찾는 알고리즘이다.

 

이 문제의 어려웠던 점은 하나로 연결된 집을 간선의 비용을 최소로 갖는 두 개의 마을로 나누는 부분이다. 처음에는 어떻게 해야 하나 감이 안잡혔지만 생각해 보니 굉장히 쉬운 문제였다. 

 

예를 들어서 아래와 같은 상황이 있다고 하쟝.

 

 

 

이와 같이 집들이 연결되어 있을때, prim이나 kruskal 알고리즘을 사용하여 MST를 구하면 오른쪽의 주황색으로 연결된 경로와 같다. 그림과 같이 집이 N개가 있을 때 간선은 N - 1개를 선택한다.

 

이때 비용을 최소로 갖는 두 개의 마을로 나누려면 결국엔 MST를 두 개로 나누는 것과 같아진다.

즉, 먼저 MST를 구해야 한다!

 

또한 MST를 두개로 나누되, 나머지 길의 비용을 최소로 하는 경로는 아래와 같다.

 

 

 

MST 중에서 가장 cost가 큰 간선을 제거하는 것이다. 위와 같이 나누는 것 보다 더 작은 cost가 되도록 나눌 수 있는 경우는 존재하지 않는다. 또한 이때 선택되는 간선은 N - 2개가 된다.

 

풀이 과정은 아래와 같다.

1. MST알고리즘으로 최소 간선 트리를 구한다.
2. 선택된 최소 간선 트리 중에서 cost가 제일 큰 값을 제외한다.

그럼, prim과 kruskal 두개의 알고리즘을 사용하여 코드를 구현해 보쟝.

 

Prim알고리즘을 사용한 구현 방법)

MST를 구하면서 가장 cost가 큰 값을 저장해 주기 위해 max변수를 사용했다.

그리고 간선을 선택할 때마다 dist값을 더해준다.

MST를 구했다면, 선택한 경로 값인 dist에서 가장 큰 cost값인 max를 빼서 반환해준다.

 

 

Kruskal알고리즘을 사용한 구현 방법)

선택하는 간선의 수를 N - 2개로 제한한다.

싸이클이 발생하지 않는 간선을 선택할 때마다 count를++해주면서 dist값을 더해준다.

N - 2개의 간선을 선택했다면 dist를 반환하면 된다.

 

코드

• prim 알고리즘

import java.util.*;
 
public class Main {    
 
    static int n, m;
    static ArrayList<Node>[] list;
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
        
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int cost = scan.nextInt();
            list[s].add(new Node(e, cost));
            list[e].add(new Node(s, cost));
        }
        
        visited = new boolean[n + 1];
        System.out.println(prim());
    }
    
    public static int prim() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(1, 0));
        int dist = 0; //현재까지의 최소 경로의 간선 합을 저장한다.
        int max = 0; //간선 중에 가장 값이 큰 간선의 값을 저장한다.
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(visited[current.n] == false) visited[current.n] = true;
            else continue;
            
            max = Math.max(max, current.cost);
            dist += current.cost;
            
            for(int i = 0; i < list[current.n].size(); i++) {
                Node next = list[current.n].get(i);
                if(visited[next.n] == false) q.offer(new Node(next.n, next.cost));
            }
        }
        return dist - max;
    }
    
    public static class Node implements Comparable<Node> {
        int n;
        int cost;
        
        public Node(int n, int cost) {
            this.n = n;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n1) {
            return this.cost - n1.cost;
        }
    }
}

 

• kruskal 알고리즘

import java.util.*;
 
public class Main {    
 
    static int n, m;
    static PriorityQueue<Node> q;
    static int[] parent;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
        
        q = new PriorityQueue<>();
        for(int i = 0; i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int cost = scan.nextInt();
            q.offer(new Node(s, e, cost));
        }
        
        parent = new int[n + 1];
        System.out.println(kruskal());
    }
    
    public static int kruskal() {
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        int count = 0;
        int dist = 0; //현재 까지의 최소 간선 경로 값의 합
        while(count < n - 2) { // n - 2개의 간선을 선택한다.
            Node node = q.poll();
            int p1 = find(node.s);
            int p2 = find(node.e);
            
            if(p1 != p2) {
                union(p1, p2);
                dist += node.cost;
                count++; // 싸이클이 발생되지 않아 최소 간선으로 선택된 경우에만 count++를 해준다.
            }
        }
        return dist;
    }
    
    public static void union(int a, int b) {
        parent[a] = b;
    }
    
    public static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
    
    public static class Node implements Comparable<Node> {
        int s;
        int e;
        int cost;
        
        public Node(int s, int e, int cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n1) {
            return this.cost - n1.cost;
        }
    }
}