문제
N개국을 모두 방문하기 위해 필요한 최소 비행기 종류 수를 구한다. 그래프는 항상 연결되어 있다.
입력
첫째 줄에 테스트 케이스 수 T가 주어진다. 각 테스트 케이스마다 N(국가 수)과 M(비행기 종류 수), M개의 노선이 주어진다.
출력
각 테스트 케이스마다 최소 비행기 종류 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 3 3 1 2 2 3 1 3 5 4 2 1 2 3 4 3 4 5 | 2 4 |
풀이
BFS로 그래프를 탐색하여 방문한 노드 수를 세고, 신장 트리의 간선 수(N-1)를 출력한다.
- 인접 행렬로 그래프를 구성한다
- 1번 노드에서 BFS를 수행하여 연결된 모든 노드를 방문한다
- 방문한 노드 수(result)에서 1을 빼면 필요한 간선 수이다
핵심 아이디어: 연결 그래프에서 모든 노드를 방문하는 최소 간선 수는 항상 N-1이다 (신장 트리 성질). 실제로는 BFS 없이 N-1만 출력해도 된다.
코드
package day549;
import java.io.*;
import java.util.*;
public class Day546BOJ9372상근이의여행 {
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);
}
}
}
}
}복잡도
- 시간: O(N^2) — 인접 행렬 기반 BFS
- 공간: O(N^2) — 인접 행렬