[백준] 9372번 상근이의 여행

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

문제 : 가장 적은 종류의 비행기로 모든 국가를 여행한다. 풀이 :  국가는 정점, 비행기는 간선 인접 행렬로 나타내서 왕복할 수 있으면 연결된 그래프이므로 1로 연결하였습니다. bfs를 활용하여 큐에 들어간 횟수를 세어줬습니다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int T, N, M, count = 0;
	static int[][] map;
	static boolean[] visited;
	static Queue<Integer> queue;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();

			map = new int[N][N];
			queue = new LinkedList();
			visited = new boolean[N];

			for (int i = 0; i < M; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				map[a - 1][b - 1] = 1;
				map[b - 1][a - 1] = 1;
			}

			bfs(0);
			System.out.println(count);
		}
	}

	public static void bfs(int i) {
		queue.offer(i);
		visited[i] = true;
		count = 0;
		while (!queue.isEmpty()) {
			int nv = queue.poll();

			for (int j = 0; j < N; j++) {
				if (map[nv][j] == 1 && !visited[j]) {
					count++;
					queue.offer(j);
					visited[j] = true;
				}
			}
		}
	}
}