[TIL][02.24] MST, Kruskal, Prim, Dijkstra

MST

Minimum Spanning Tree (최소 신장 트리)

최단 경로는 특정 두 노드 간의 거리를 최소화하는 것

MST는 모든 노드를 연결하면서 총 가중치를 최소화하는 것

예시:

-도로 건설 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제

-전기 회로 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제

-통신 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제

-배관 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

 

Kruskal

대표적인 그리디 알고리즘

1. 간선 정렬

2. 사이클이 없는 간선 선택

Parent배열에 각 정점에 자기 자신이 저장되어 있으면 현재 서로소라는 뜻(간선을 선택하지 않음)

간선 선택 시 Parent 배열 업데이트

간선이 많으면 크루스칼에서는 정렬에 시간이 많이 든다. 이럴때는 정점 기반 처리를 하는 프림을 쓴다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class kruskal {

	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		String []nm=br.readLine().split(" ");
		int N=Integer.parseInt(nm[0]);
		int M=Integer.parseInt(nm[1]);
		
		Edge []arr=new Edge[M];
		for (int i = 0; i < M; i++) {
			String []ftw=br.readLine().split(" ");
			int from=Integer.parseInt(ftw[0]);
			int to=Integer.parseInt(ftw[1]);
			int weight=Integer.parseInt(ftw[2]);
			arr[i]=new Edge(from, to, weight);
		}
		Arrays.sort(arr);
		makeSet(N);
		int result = 0;
		int pickCnt = 0;
		
		for(Edge e:arr) {
			if(union(e.f, e.t)) {
				result += e.w;
				if(++pickCnt==(N-1))break;
			}
		}
		
		System.out.println(result);
	}
	static boolean union(int f,int t) {
		int fp=find(f);
		int tp=find(t);
		if(fp==tp) return false;
		
		p[tp]=fp;
		return true;
	}
	
	static int find(int e) {
		if(e!=p[e]) p[e]=find(p[e]);
		return p[e];
	}
	
	static int[]p;
	static void makeSet(int V) {
		p=new int[V + 1];
		for (int i = 1; i < V; i++) {
			p[i]=i;
		}
	}
	
	static class Edge implements Comparable<Edge>{
		int f,t,w;

		public Edge(int f, int t, int w) {
			super();
			this.f = f;
			this.t = t;
			this.w = w;
		}

		@Override
		public String toString() {
			return "Edge [f=" + f + ", t=" + t + ", w=" + w + "]";
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(w, o.w);
		}
		
		
		
	}

}

• arr에 간선 정보 저장
• 간선을 최솟값부터 처리하기위해 정렬
• 사이클 확인을 위한 배열 p 구현 및 자기자신으로 초기화
• arr의 첫번째 값부터 하나씩 꺼내고 find메서드로 루트를 확인해서 union 메서드에서 사이클이 생성되면 다음 간선으로 넘어가고, 그렇지 않으면 가중치 합에 추가하고, p배열 업데이트
• 선택한 간선의 개수가 정점의 개수-1이 될 때까지 실행

Prim

1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.

2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선(PriorityQueue이용하면 쉬움)으로 연결된 정점을 선택하여 트리를 확장한다.즉, 가장 낮은 가중치를 먼저 선택한다.

3. 모든 정점이 선택되었으면 끝냄.

package graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class 문제1_prim_0225 {
    static class Edge implements Comparable<Edge> {
        int to, weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

    static List<List<Edge>> graph;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 입력 받기
        String[] nm = br.readLine().split(" ");
        int N = Integer.parseInt(nm[0]);  // 정점 개수
        int M = Integer.parseInt(nm[1]);  // 간선 개수

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

        // 간선 정보 저장 (인접 리스트)
        for (int i = 0; i < M; i++) {
            String[] ftw = br.readLine().split(" ");
            int from = Integer.parseInt(ftw[0]);
            int to = Integer.parseInt(ftw[1]);
            int weight = Integer.parseInt(ftw[2]);

            graph.get(from).add(new Edge(to, weight));
            graph.get(to).add(new Edge(from, weight)); // 무방향 그래프
        }

        // 프림 알고리즘 실행
        System.out.println(prim(N));
    }

    static int prim(int N) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        visited = new boolean[N + 1]; // 방문 여부 체크
        pq.add(new Edge(1, 0)); // 시작 정점 (1번 노드 선택)

        int result = 0; // MST 비용 합
        int count = 0; // 선택된 간선 개수

        while (!pq.isEmpty()) {
            Edge now = pq.poll(); // 가장 작은 비용의 간선 선택

            if (visited[now.to]) continue; // 이미 방문한 정점이면 무시

            visited[now.to] = true; // 방문 처리
            result += now.weight;
            count++;

            if (count == N) break; // 모든 정점이 연결되면 종료

            // 선택된 정점과 연결된 간선들 추가
            for (Edge next : graph.get(now.to)) {
                if (!visited[next.to]) {
                    pq.add(next);
                }
            }
        }

        return result;
    }
}

• graph에 간선 정보 저장
• 우선순위 큐에 처리할 간선을 가중치 기준 오름차순 정렬하여 관리
• visited[] 배열을 사용하여 방문 여부를 체크한다.
• 우선순위 큐에서 최소 비용 간선을 꺼내어 정점 추가, 비용 더함
• 이미 방문한 정점이면 스킵
• count == N - 1이 되면 모든 정점이 연결되었으므로 종료

Dijkstra

프림 알고리즘은 모든 정점을 연결하는 최소비용 구하기 알고리즘이고, 다익스트라는 특정 시작점에서 특정 도착점까지의 최소비용 구하기 알고리즘이다.

• 프림의 visited[]는 단순 방문 여부 체크지만, 다익스트라는 최단 거리를 저장해야 하므로 dist[]을 사용
• (거리, 정점) 형태로 저장해야 하므로 pq.add(new Edge(거리, 정점))로 변경
• 큐에서 꺼낼 때 방문 여부 대신 최단 거리 갱신 여부 체크 (기존 거리보다 크면 무시)

그룹 과제

MST 문제 1

문제 1: 최소 비용 도로 건설

문제 설명

어떤 나라에는 N개의 도시가 있고, 일부 도시들은 도로로 연결되어 있다. 정부는 모든 도시를 최

소한의 비용으로 연결하려 한다. 각 도로는 두 도시를 연결하며 특정 비용이 든다. 모든 도시를

연결하는 최소 비용을 구하시오.

입력

첫 번째 줄에 도시의 개수 N과 도로의 개수 M이 주어진다.

다음 M개의 줄에는 u,v,k 가 주어지며, 이는 도시 u와 도시 v를 연결하는 도로의 비용이 k임을

의미한다.

출력

모든 도시를 연결하는 최소 비용을 출력하시오.

제한

1≤N≤10^5

1≤M≤2×10^5

1≤k≤10^6

예시

입력 :

4 5

1 2 1

1 3 2

1 4 3

2 3 1

3 4 1

출력 :

3

크루스칼 풀이

package graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 문제1_kruskal_0224 {

	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		String []nm=br.readLine().split(" ");
		int N=Integer.parseInt(nm[0]);
		int M=Integer.parseInt(nm[1]);
		
		Edge []arr=new Edge[M];
		for (int i = 0; i < M; i++) {
			String []ftw=br.readLine().split(" ");
			int from=Integer.parseInt(ftw[0]);
			int to=Integer.parseInt(ftw[1]);
			int weight=Integer.parseInt(ftw[2]);
			arr[i]=new Edge(from, to, weight);
		}
		Arrays.sort(arr);
		makeSet(N);
		int result = 0;
		int pickCnt = 0;
		
		for(Edge e:arr) {
			if(union(e.f, e.t)) {
				result += e.w;
				if(++pickCnt==(N-1))break;
			}
		}
		
		System.out.println(result);
	}
	static boolean union(int f,int t) {
		int fp=find(f);
		int tp=find(t);
		if(fp==tp) return false;
		
		p[tp]=fp;
		return true;
	}
	
	static int find(int e) {
		if(e!=p[e]) p[e]=find(p[e]);
		return p[e];
	}
	
	static int[]p;
	static void makeSet(int V) {
		p=new int[V + 1];
		for (int i = 1; i < V; i++) {
			p[i]=i;
		}
	}
	
	static class Edge implements Comparable<Edge>{
		int f,t,w;

		public Edge(int f, int t, int w) {
			super();
			this.f = f;
			this.t = t;
			this.w = w;
		}

		@Override
		public String toString() {
			return "Edge [f=" + f + ", t=" + t + ", w=" + w + "]";
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(w, o.w);
		}
		
		
		
	}

}

프림 풀이

package graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class 문제1_prim_0225 {
    static class Edge implements Comparable<Edge> {
        int to, weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

    static List<List<Edge>> graph;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] nm = br.readLine().split(" ");
        int N = Integer.parseInt(nm[0]); 
        int M = Integer.parseInt(nm[1]);

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

        for (int i = 0; i < M; i++) {
            String[] ftw = br.readLine().split(" ");
            int from = Integer.parseInt(ftw[0]);
            int to = Integer.parseInt(ftw[1]);
            int weight = Integer.parseInt(ftw[2]);

            graph.get(from).add(new Edge(to, weight));
            graph.get(to).add(new Edge(from, weight));
        }

        System.out.println(prim(N));
    }

    static int prim(int N) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        visited = new boolean[N + 1];
        pq.add(new Edge(1, 0));

        int result = 0;
        int count = 0;

        while (!pq.isEmpty()) {
            Edge now = pq.poll();

            if (visited[now.to]) continue;

            visited[now.to] = true;
            result += now.weight;
            count++;

            if (count == N) break;

            for (Edge next : graph.get(now.to)) {
                if (!visited[next.to]) {
                    pq.add(next);
                }
            }
        }

        return result;
    }
}

MST 문제 2

문제 2: 전력망 복구

문제 설명

어떤 나라에는 N개의 발전소와 전력망이 있으며, 일부 발전소는 전력을 공급하기 위해 전력망을

통해 다른 발전소와 연결되어 있다. 자연 재해로 일부 전력망이 파손되어 복구가 필요하다. 정부

는 최소한의 비용으로 전력망을 복구하여 모든 발전소가 전력을 공급받을 수 있도록 해야 한다.

각 전력망의 복구 비용이 다르고, 두 발전소를 연결할 수 있는 여러 가지 전력망이 존재한다. 최

소 비용으로 전력망을 복구하는 방법을 구하시오.

입력

첫 번째 줄에 발전소의 개수 N과 전력망의 개수 M이 주어진다.

다음 M개의 줄에는 u,v,k가 주어지며, 이는 발전소 u와 발전소 v를 연결하는 전력망의 복구 비용

이 k임을 의미한다.

출력

모든 발전소를 연결하는 최소 비용을 출력하시오.

제한

2≤N≤10^5

1≤M≤2×10^5

1≤w≤10^6

예시

입력 :

5 6

1 2 3

1 3 4

2 3 1

2 4 2

3 4 5

4 5 6

출력 :

12

풀이

문제 1 풀이와 동일

개인과제

프로그래머스 Lv.2 (1)

[JS]프로그래머스 - 프로세스 (Lv.2)

 

프로그래머스 Lv.2 (2)

[JS]프로그래머스 - 피로도 (Lv.2)