섹션 9 Greedy - 7. 원더랜드(최소스패닝트리 - 프림, PriorityQueue)

문제 설명

원더랜드는 모든 도시를 유지하면서 최소 비용만으로 도로를 연결하려고 한다.
즉, 모든 도시를 연결하는데 드는 최소 유지비용을 구해야 한다.
이는 최소 스패닝 트리(MST) 문제이며, 두 가지 알고리즘 중 하나인 프림 알고리즘으로 해결할 수 있다.

---

입력

• 첫째 줄: 도시의 개수 V(1 ≤ V ≤ 100), 도로의 개수 E(1 ≤ E ≤ 1,000)
• 이후 E줄: 각 줄마다 세 정수 A, B, C (A번 도시와 B번 도시가 유지비용 C인 도로로 연결됨)

---

출력

• 모든 도시를 연결할 수 있는 최소 유지비용 출력

---

예시 입력

 

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

예시 출력

 

196

---

해결 방법

• 우선순위 큐(PriorityQueue) 와 프림 알고리즘을 사용해서 최소 비용의 간선부터 선택
• 방문 여부 체크 배열을 통해 이미 연결된 도시를 중복해서 연결하지 않도록 방지
• 선택된 도시에 인접한 도시들 중, 아직 방문하지 않은 도시들을 큐에 추가하며 반복

---

코드 구현 (프림 알고리즘 기반)

import java.util.*;

class Edge2 implements Comparable<Edge2> {
	public int vex, cost;
	Edge2(int vex, int cost) {
		this.vex = vex;
		this.cost = cost;
	}
	@Override
	public int compareTo(Edge2 ob) {
		return this.cost - ob.cost;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 도시 수
		int m = sc.nextInt(); // 도로 수

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

		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			graph.get(a).add(new Edge2(b, c));
			graph.get(b).add(new Edge2(a, c)); // 양방향 연결
		}

		int answer = 0;
		int[] ch = new int[n + 1];
		PriorityQueue<Edge2> pQ = new PriorityQueue<>();
		pQ.offer(new Edge2(1, 0)); // 시작점은 1번 도시

		while (!pQ.isEmpty()) {
			Edge2 tmp = pQ.poll();
			int ev = tmp.vex;
			if (ch[ev] == 0) {
				ch[ev] = 1;
				answer += tmp.cost;
				for (Edge2 ob : graph.get(ev)) {
					if (ch[ob.vex] == 0) {
						pQ.offer(new Edge2(ob.vex, ob.cost));
					}
				}
			}
		}
		System.out.print(answer);
		sc.close();
	}
}

---

코드 설명

class Edge2 implements Comparable<Edge2> {
	public int vex, cost;
	Edge2(int vex, int cost) {
		this.vex = vex;
		this.cost = cost;
	}
	@Override
	public int compareTo(Edge2 ob) {
		return this.cost - ob.cost; // 비용 기준 오름차순 정렬
	}
}

 

• Edge2 클래스는 우선순위 큐에서 비용이 적은 간선을 먼저 선택할 수 있도록 Comparable 인터페이스 구현
• vex: 연결될 도시 번호
• cost: 해당 간선을 통해 연결하는 데 드는 유지비용

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

 

• graph는 인접 리스트 형태로, 각 도시(1~n)가 연결된 간선 정보를 저장
• 도시 번호는 1부터 시작하므로 인덱스를 0~n까지 생성

for (int i = 0; i < m; i++) {
	int a = sc.nextInt();
	int b = sc.nextInt();
	int c = sc.nextInt();
	graph.get(a).add(new Edge2(b, c));
	graph.get(b).add(new Edge2(a, c)); // 양방향 도로이므로 반대 방향도 추가
}

 

• 간선 입력을 받고, 양방향 간선이므로 두 방향 모두 그래프에 추가한다.
• graph.get(a)는 도시 a에서 연결된 간선 리스트를 의미한다.

int answer = 0;
int[] ch = new int[n + 1];
PriorityQueue<Edge2> pQ = new PriorityQueue<>();
pQ.offer(new Edge2(1, 0)); // 1번 도시를 시작점으로 큐에 삽입

 

• answer: 최종 최소 비용을 누적할 변수
• ch: 도시 방문 여부를 체크하는 배열 (0이면 미방문, 1이면 방문 완료)
• pQ: 비용이 적은 간선부터 꺼내기 위한 우선순위 큐
• 시작점은 1번 도시로 지정

while (!pQ.isEmpty()) {
	Edge2 tmp = pQ.poll();
	int ev = tmp.vex;

	if (ch[ev] == 0) { // 아직 방문하지 않은 도시인 경우
		ch[ev] = 1; // 방문 처리
		answer += tmp.cost; // 유지비용 누적

		for (Edge2 ob : graph.get(ev)) {
			if (ch[ob.vex] == 0) { // 연결된 도시가 미방문이면 큐에 추가
				pQ.offer(new Edge2(ob.vex, ob.cost));
			}
		}
	}
}

• 프림 알고리즘 핵심 부분
  • 현재 선택된 간선이 연결하는 도시가 아직 방문하지 않은 도시일 경우에만 선택.
  • 해당 도시에서 연결 가능한 다른 도시들의 간선을 큐에 넣는다.
  • 큐에서는 항상 비용이 가장 낮은 간선부터 꺼내므로 전체 비용이 최소화된다.

 

---

시간 복잡도

• E: 전체 간선 수
• V: 전체 정점 수
• 우선순위 큐에서 간선을 넣고 뺄 때마다 log V 시간 걸림
• 모든 간선을 최대 한 번씩 처리하므로 총 E번 처리 × log V → O(E log V)

→ PriorityQueue와 정점 탐색 비용이 포함된 프림 알고리즘의 일반적인 시간 복잡도

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런