[MST] 백준 1922번 네트워크 연결 - JAVA (프림 & 크루스칼 2가지 풀이)

 

오늘 수업 끝나기 1시간 전에 선택한 문제

프림으로 풀라다가 생각안나서 다익스트라로 풀었는데,

민성이 오빠의 이해할 수 없다는 표정과

호진이 오빠의 웃음소리가 선명하다.

시무룩

 

MST 문제를 풀기 위해 내가 선택할 수 있는 알고리즘은

프림과 크루스칼 둘 중 하나였는데,

간지나 보인다고 크루스칼로 풀라는 오빠들의 말을 뒤로하고, 프림으로 풀 것이다.

 

 

+23.04.16 추가

시험공부하면서 크루스칼로도 풀어보았다.

 

---

1. 문제 출처

---

 

 

1922번: 네트워크 연결

 

 

 

 

---

2. 설계

---

 

 

모든 노드를 최소 비용으로 연결해야 하기 때문에 MST 문제이고, 크루스칼 또는 프림으로 풀어야 한다. (그 외 더 방법이야 있겠지만 나는 이 둘만 안다.) 그래서 오늘 문제를 통해 프림을 복습하고, 그대로 적용하니 정답으로 이어졌다. 

 

 

- 프림 설계

 

public static void prim(int start) {
		boolean[] visited = new boolean[N+1];
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		
		//첫 노드 처리
		visited[start]=true;
		pq.addAll(adjList[start]);
		
		int pick = 1;
		
		while(pick!=N) {
			
			Edge cur = pq.poll();
			
			if(visited[cur.num]) continue;//이 노드가 이미 방문되었다면 선택 안함
			
			//방문 안된 노드라면 선택함
			pick++;
			result+=cur.fee;
			
			//해당 노드에 연결된 모든 노드들을 pq에 넣는다.
			visited[cur.num]=true;
			pq.addAll(adjList[cur.num]);
			
		}
	}

 

1) 첫 방문할 노드를 선정한다.

- 꼭 1번 노드가 아니어도 된다.

 

 

2) 첫 노드를 방문처리하고, PriorityQueue에 인접 노드들을 모두 넣는다.

- 첫 노드에서 갈 다음 노드를 선택함으로써 간선(길)이 채택되는 것이다.

- 노드 중 시작점을 채택한 격이기 때문에 pick을 하나 추가한다. 1부터 시작한다.

 

 

3) 결국 N(노드 수)-1만큼의 간선이 채택되면 MST가 완성되는 것이다.

- 왜냐하면 최소 간선의 수는 노드수 - 1이기 때문이다. 이처럼 (a - b) a, b의 두 정점을 연결하는데 간선이 1개 필요한 것 처럼 말이다. 

- while로 그만큼을 뽑을 때까지 돌린다.

 

 

4) PriorityQueue에서 가장 비용이 적은 노드를 하나 꺼낸다.

- 근데 만약 이 노드가 방문되었던 노드라면 이 노드를 채택하지 않는다.

- 방문 되지 않았던 노드라면 기꺼이 채택한다. 왜냐? 우선순위 큐에서 가장 작은 비용이 먼저 튀어나오기 때문에 방문하지 않은 노드라면 바로 채택해야하는 것이다.

- 채택하는 노드라면 pick을 1추가해주고, 결과 비용에 추가해준다.

- 채택하는 노드라면 해당 노드와 인접한 노드들 전부를 우선순위 큐에 넣어준다. (다음 경로를 탐색하기 위함이다.)

- 채택하는 노드라면 마지막에 방문처리는 꼭 해준다.

 

 

프림은 기본적으로 무향그래프를 다루기 때문에 방문 체크는 필수이다.

 

 

23.04.18 추가

- 크루스칼 설계

크루스칼에는 꼭 알아야할 주요 3가지 메서드가 있다.

 

1) set함수

본격적으로 크루스칼을 돌리기 이전에 자기 자신을 부모로 셋팅한다.

public static void set() {
	for(int i=1;i<=N;i++) {
		p[i]=i;
		rank[i]=0;
	}
}

 

2) myP함수

나의 진짜 부모를 찾아주는 함수이다.

내 부모가 나와 같으면 내가 부모라는 뜻이기 때문에 나를 반환해준다.

만약 내 부모가 나와 다르면, 트리를 타고타고 올라가 나의 시초 부모를 찾아준다.

public static int myP(int node) {
	if(p[node]==node) return node;
	return p[node]=myP(p[node]);
}

 

 

3) Union함수

두 노드를 연결해주는 함수이다. 크루스칼에서 두 노드를 연결한다는 뜻은 두 부모를 같게해주겠다는 뜻과 같다. 때문에 연결 전 두 노드의 부모를 찾아주고, 두 부모가 이미 같다면 작업해줄 필요가 없다. 하지만 두 노드의 부모가 다르다면 두 노드의 부모 중 어떤 부모가 힘이 센지 판단(rank)한 후 힘이 센 부모 밑에 힘이 덜 센 부모를 속하게 한다.

public static void Union(int node1, int node2) {
	int node1P = myP(node1);
	int node2P = myP(node2);
		
	if(node1P!=node2P) {
		if(rank[node1P]>rank[node2P]) {
			p[node2P]=node1P;
		}else {
			p[node1P]=node2P;
			if(node1P==node2P) {
				rank[node2P]++;
			}
		}
	}
}

 

 

4) 본격적인 코드 시작

edgeList는 priority queue로 비용이 작은 순으로 간선들이 나열되어 있다. 때문에 가장 비용이 작은 간선에 있는 노드 두개를 비교하며 부모가 다르다면 이 둘을 연결시켜주는 작업을 진행한다. 하지만 부모가 같다면 이들은 이미 연결되어 있다는 뜻으로 해당 간선을 채택하지 않는다.

while(!edgeList.isEmpty()) {
	Edge cur = edgeList.poll();
	int front = cur.startNode;
	int end = cur.endNode;
	int fee = cur.fee;
			
	if(myP(front)==myP(end)) {
		continue;
	}
	else {
		//간선 채택 
		Union(front, end);
		result += cur.fee;	
	}
}
System.out.println(result);

 

 

---

3. 전체코드 (프림)

---

package 백준1922;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 네트워크연결 {
	static List<Edge>[] adjList;
	static int N,M,result;
	static class Edge implements Comparable<Edge>{
		int num;
		int fee;
		public Edge(int num, int fee) {
			super();
			this.num = num;
			this.fee = fee;
		}
		@Override
		public int compareTo(Edge o) {
			return this.fee>o.fee?1:-1;
		}
		@Override
		public String toString() {
			return "Edge [num=" + num + ", fee=" + fee + "]";
		}
		
		
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();//컴퓨터수
		M = sc.nextInt();//간선 수
		
		//초기화
		adjList = new ArrayList[N+1];
		for(int i=0;i<N+1;i++) {
			adjList[i] = new ArrayList<>();
		}
		
		for(int i=0;i<M;i++) {
			int startNode = sc.nextInt();
			int endNode = sc.nextInt();
			int fee = sc.nextInt();
			
			//무향
			adjList[startNode].add(new Edge(endNode,fee));
			adjList[endNode].add(new Edge(startNode,fee));
		}
		prim(1);
		System.out.println(result);

	}
	
	public static void prim(int start) {
		boolean[] visited = new boolean[N+1];
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		
		//첫 노드 처리
		visited[start]=true;
		pq.addAll(adjList[start]);
		
		int pick = 1;
		
		while(pick!=N) {
			
			Edge cur = pq.poll();
			
			if(visited[cur.num]) continue;//이 노드가 이미 방문되었다면 선택 안함
			
			//방문 안된 노드라면 선택함
			pick++;
			result+=cur.fee;
			
			//해당 노드에 연결된 모든 노드들을 pq에 넣는다.
			visited[cur.num]=true;
			pq.addAll(adjList[cur.num]);
			
		}
	}

}

 

 

---

3. 전체코드 (크루스칼)

---

23.04.16 추가

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static Queue<Edge> edgeList;
	static int[] p;//부모 
	static int[] rank;
	static int N,M;
	
	static class Edge implements Comparable<Edge>{
		int startNode;
		int endNode;
		int fee;
		public Edge(int startNode, int endNode, int fee) {
			super();
			this.startNode = startNode;
			this.endNode = endNode;
			this.fee = fee;
		}
		@Override
		public int compareTo(Edge o) {
			return this.fee>o.fee?1:-1;
		}		
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N =sc.nextInt();//컴퓨터의 수 
		M = sc.nextInt();//선의 수
		
		//초기화
		p = new int[N+1];
		rank = new int[N+1];
		edgeList = new PriorityQueue<>();
		
		for(int i=0;i<M;i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int fee = sc.nextInt();
			
			//무향->유향으로 해야 값이 2배 안됨
			edgeList.add(new Edge(a,b,fee));
			//edgeList.add(new Edge(b,a,fee));
		}
		
		//데이터 입력 끝
		
		set();
		long result = 0L;
		while(!edgeList.isEmpty()) {
			Edge cur = edgeList.poll();
			int front = cur.startNode;
			int end = cur.endNode;
			int fee = cur.fee;
			
			if(myP(front)==myP(end)) {
				continue;
			}
			else {
				//간선 채택 
				Union(front, end);
				result += cur.fee;	
			}
		}
		System.out.println(result);	
	}
	
	public static void set() {
		for(int i=1;i<=N;i++) {
			p[i]=i;
			rank[i]=0;
		}
	}
	
	public static int myP(int node) {
		if(p[node]==node) return node;
		return p[node]=myP(p[node]);
	}
	
	public static void Union(int node1, int node2) {
		int node1P = myP(node1);
		int node2P = myP(node2);
		
		if(node1P!=node2P) {
			if(rank[node1P]>rank[node2P]) {
				p[node2P]=node1P;
			}else {
				p[node1P]=node2P;
				if(node1P==node2P) {
					rank[node2P]++;
				}
			}
		}
	}

}

무향으로하면 결과값이 2배가 된다.

문제의 테스트 케이스에서는 2배가 안되지만,  예를 들어 아래 테스트 케이스로 해보면 값이 2배가 되는 것을 확인할 수 있을 것이다.

답은 전체 1~4가 연결된 경로의 최소비용 2 + 3 + 4 = 9가 나와야 한다.

 

4
3
1 2 2
2 3 3
1 4 4

 

 

---

 

알고리즘 수업 끝났다고 방심하지 말자.

다시 복습해!!!