MST와 최단경로 정리

gw07167·2023년 9월 30일
MST최단경로
0

알고리즘

목록 보기
2/2

MST

최소신장트리 : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치들의 합이 최소인 신장 트리

정점의 개수가 N일때 N(N-1)/4 -> N^2/4를 기준으로 간선이 많다 적다를 판단한다

  • 간선이 적으면 Kruskal
  • 간선이 많으면 Prim

1. Kruskal

간선중심으로 최소신장트리를 구하는 방법이다

가중치가 작은 간선부터 하나씩 선택하며 정점을 연결한다

O(ElogE)의 시간복잡도를 가진다

싸이클이 생기지 않도록 연결하기 위해 Union Find 알고리즘을 적용하여 사이클 발생 여부를 확인한다

  1. 모든 간선을 가중치에 따라 오름차순으로 정렬
  2. 가중치가 가장 작은 간선부터 선택하면서 트리를 증가시킴
  3. N-1개가 모두 선택되면 종료

[크루스칼 문제 목록]

  • BOJ 1179 최소 스패닝 트리
  • BOJ 4386 별자리 만들기
  • SWEA 3124 최소 스패닝 트리
  • SWEA 1251 하나로
  • SWEA 7465 창용 마을 무리의 개수
  • BOJ 17472 다리 만들기2

BOJ 1197 최소 스패닝 트리

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

public class Main {
	
	static int V,E;
	static long min;
	static class Edge implements Comparable<Edge> {
		int s;
		int e;
		int w;
		public Edge(int s, int e, int w) {
			super();
			this.s = s;
			this.e = e;
			this.w = w;
		}
		
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.w, o.w);
		}
		
	}
	static PriorityQueue<Edge> points;
	// kruskal
	static int[] p;
	static int[] r;
	
	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());
		points = new PriorityQueue<>();
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			points.offer(new Edge(s, e, w));
		}
		p = new int[V+1];
		r = new int[V+1];
		makeSet();
		int cnt = 0; // V-1회 반복
		min=0;
		while(cnt!=V-1) {
			Edge edge = points.poll();
			if(union(edge.s, edge.e)) {
				cnt++;
				min += edge.w;
			}
		}
		System.out.println(min);
	}

	static boolean union(int x, int y) {
		x=find(x);
		y=find(y);
		if(x==y) return false; // Cycle 발생
		if(r[x]>=r[y]) {
			r[x]+=r[y];
			p[y]=x;
		} else {
			r[y]+=r[x];
			p[x]=y;
		}
		return true;
	}

	static int find(int x) {
		if(x==p[x]) return p[x];
		else return p[x] = find(p[x]);
	}

	static void makeSet() {
		for(int i = 0; i <= V; i++) {
			p[i] = i;
			r[i] = 1;
		}
	}

}

2. Prim

정점중심으로 최소신장트리를 구하는 방법이다

Priority를 활용하여 임의의 정점에서 인접하면서 아직 선택되지 않은 정점 중에 가장 가중치가 작은 간선을 연결한다

O(ElogV)의 시간복잡도를 가진다

  1. 임의의 정점을 하나 선택해서 시작한다
  2. 선택한 정점과 인접한 정점들 중에 최소 비용의 간선이 존재하는 정점을 선택한다
  3. 모든 정점이 선택될 때까지 반복한다

[프림 문제 목록]

  • BOJ 1179 최소 스패닝 트리
  • SWEA 1251 하나로

BOJ 1197 최소 스패닝 트리

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

public class Main {
	
	static int V,E;
	static Long min;
	static class Edge implements Comparable<Edge> {
		int v;
		int w;
		
		public Edge(int v, int w) {
			this.v = v;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.w, o.w);
		}
		
	}
	static PriorityQueue<Edge> points;
	// prim
	static List<Edge>[] adj;
	
	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());
		points = new PriorityQueue<>();
		
		adj = new ArrayList[V+1];
		for(int i = 0; i < V+1; i++) {
			adj[i]= new ArrayList<>();
		}
		
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			adj[s].add(new Edge(e, w));
			adj[e].add(new Edge(s, w));
		}
		System.out.println(prim());
	}

	static long prim() {
		min = 0L;
		boolean[] visited = new boolean[V+1]; // prim의 아이디어
		points.offer(new Edge(1, 0)); // 임의의 정점 시작 가능
		int cnt = 0;
		while(!points.isEmpty()) {
			Edge edge = points.poll();
			if(visited[edge.v]) continue;
			min += edge.w;
			visited[edge.v] = true; 
			if(++cnt==V) return min; // cnt == V-1, V-1 모두 찾으면
			for(int i = 0; i < adj[edge.v].size(); i++) {
				Edge next = adj[edge.v].get(i);
				if(visited[next.v]) continue;
				points.offer(next);
				
			}
		}
		return min;
	}


}

최단경로

최단경로 : 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들중 간선의 가중치의 합이 최소인 경로

1. 다익스트라

다익스트라 : 시작 정점에서의 거리가 최소인 정점을 선택해나가며 경로를 구하는 방식

distance 배열, PriorityQueue, adj리스트를 사용한다.

  1. 시작 노드의 거리를 0으로 초기화 후 우선순위 큐에 담음
  2. 나머지 노드의 distance 배열 값은 무한대로 초기화
  3. 우선순위 큐에서 pop한 후 그 노드에서 갈 수 있는 노드를 확인
  4. 더 빠르다면 갱신하고 우선순위 큐에 넣는다
  5. 방문했거나, 더 느리다면 continue
  6. 우선순위 큐가 빌 때까지 3-5번을 반복한다

[다익스트라 문제 목록]

  • BOJ 1753 최단경로
  • BOJ 4485 녹색 옷 입은 애가 젤다지?
  • BOJ 5972 택배 배송

BOJ 1753 최단경로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int V, E, K;
	static int[] distance;
	static boolean[] visited;
	
	static class Edge implements Comparable<Edge>{
		int v;
		int w;
		
		public Edge(int v, int w) {
			this.v = v;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.w, o.w);
		}
	}
	static List<Edge>[] adj;
	static int MM=Integer.MAX_VALUE/1000;
	static PriorityQueue<Edge> points;
	
	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());
		K=Integer.parseInt(br.readLine());
		adj=new ArrayList[V];
		for(int i = 0; i < V; i++) {
			adj[i] = new ArrayList<>();
		}
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			adj[s-1].add(new Edge(e-1, w));
		}
		distance = new int[V];
		Arrays.fill(distance, MM); // 무한으로 초기화
		visited = new boolean[V];
		points = new PriorityQueue<>();
		points.offer(new Edge(K-1, 0));
		distance[K-1]=0; // 시작을 0으로 놓는다!
		while(!points.isEmpty()) {
			Edge cur = points.poll();
			if(visited[cur.v]) continue;
			visited[cur.v]=true;
			for(Edge nxt : adj[cur.v]) {
				if(visited[nxt.v]) continue;
				if(distance[nxt.v] > distance[cur.v]+nxt.w) { // 여기만 다르다
					distance[nxt.v]= distance[cur.v]+nxt.w;
					points.offer(new Edge(nxt.v, distance[nxt.v]));
				}
			}
		}
		// k -> i
		for(int i = 0; i < V; i++) {
			if(distance[i]>=MM) {
				System.out.println("INF");
			} else {
				System.out.println(distance[i]);
			}
		}
	}

}

플로이드 워샬

플로이드 워샬 : 모든 쌍의 최단 경로를 찾는 동적 계획 알고리즘

음의 가중치도 가능하다.

dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
정점 i,j 사이의 모든 경유지를 탐색해서 그 중 최단 경로를 찾아내는 것이다.

O(N^3) 시간복잡도를 가진다

  1. 인접 행렬을 저장할 2차원 배열을 만들고 무한대로 초기화
  2. 간선정보를 저장하고, 제자리는 0으로 초기화
  3. 경유지를 기준으로, 해당 경유지를 거쳐가는게 빠르다면 갱신
  4. 모든 정점을 경유지를 선정해 3번 반복

[플로이드 워샬 문제 목록]

  • SWEA 1263 사람 네트워크2
  • BOJ 9205 맥주 마시면서 걸어가기
  • SWEA 5643 키 순서

SWEA 1263 사람 네트워크2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

	static int T;
	static int N;
	static int[][] adj;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			adj = new int[N+1][N+1];
			for(int i = 1; i <= N; i++) {
				for(int j = 1; j <= N; j++) {
					adj[i][j] = Integer.parseInt(st.nextToken());
					if(i == j) continue;
					if(adj[i][j] == 0) adj[i][j] = 1000;
				}
			} // 입력 끝
			
			// 플로이드 워샬
			for(int k = 1; k <= N; k++) {
				for(int i = 1; i <= N; i++) {
					for(int j = 1; j <= N; j++) {
						if(i == j || i == k || j == k) continue;
						adj[i][j] = Math.min(adj[i][j], adj[i][k]+adj[k][j]);
					}
				}
			}
			
			int ans = 5000;
			for(int i = 1; i <= N; i++) {
				int sum = 0;
				for(int j = 1; j <= N; j++) {
					sum += adj[i][j];
				}
				ans = Math.min(ans, sum);
			}
			sb.append("#"+t+" "+ans+"\n");
			
		}
		System.out.println(sb.toString());
	}

}
profile
이전 포스트

KMP 알고리즘

0개의 댓글