Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

30. 최소 신장 트리

최소 비용으로 그래프의 모든 정점을 연결해 봅시다.

---

Java / Python

1. 상근이의 여행

9372번

신장 트리가 중요한 이유는, 가장 적은 개수의 간선으로 모든 정점을 연결할 수 있기 때문입니다. 이 문제를 통해 확인해 봅시다.

이번 문제는 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주는 문제로, 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

최소 신장 트리의 성질을 이용한다. 간선의 개수는 정점의 개수-1 이다.
즉, 모든 국가가 연결되어 있기 때문에 비행기 종류의 최소 개수는 국가 수 - 1이다.

BFS나 DFS를 활용할 수도 있다.

• Java

최소 신장 트리의 성질 이용

import java.io.*;
import java.util.*;

public class Main {
	static int N, M;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());

		while (T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			for (int i = 0; i < M; i++) {
				br.readLine();
			}
			sb.append((N-1) + "\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}

BFS 활용

import java.io.*;
import java.util.*;

public class Main {
	static int[][] plane;
	static boolean[] visit;
	static int N, M, result;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		while (T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			result = 0;

			plane = new int[N + 1][N + 1];
			visit = new boolean[N + 1];

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());

				plane[u][v] = 1;
				plane[v][u] = 1;
			}
			bfs();
			bw.write(result - 1 + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	public static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		visit[1] = true;
		while (!queue.isEmpty()) {
			result++;
			int value = queue.poll();
			for (int i = 1; i <= N; i++) {
				if (plane[value][i] != 0 && !visit[i]) {
					visit[i] = true;
					queue.add(i);
				}
			}
		}
	}
}

• Python

최소 신장 트리의 성질 이용

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    for _ in range(M):
        u, v = map(int, input().split())
    print(N - 1)

DFS 활용

import sys
input = sys.stdin.readline

def dfs(node, cnt):
    visit[node] = 1
    for i in Tree[node] :
        if visit[i] == 0:
            cnt = dfs(i, cnt+1)
    return cnt

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    Tree = [[] for _ in range(N+1)]
    
    for _ in range(M):
        u, v = map(int, input().split())
        Tree[u].append(v)
        Tree[v].append(u)

    visit = [0] * (N+1)
    visit[1] = 0
    result = dfs(1, 0)
    print(result)

---