#백준_9372 상근이의 여행 - Java 자바

#유형 : 그래프 탐색, BFS

# 난이도 : 실버 4

# BFS에 대한 개념이 잘 잡혀있다면, 문제만 봐도 BFS로 바로 풀 수 있다는 것을 알 수 있다. 아래 코드에서 result는 방문한 곳을 체크한것이다. 예를 들어 3개의 지역을 방문하려면 2(3-1)개의 비행기를 타야하므로 result-1 을 출력한다.

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p9372 {
    static int N,M,result;
    static boolean visit[];
    static int arr[][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        for(int tc=0; tc<testCases; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            result = 0;
            
            arr = 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());
                arr[u][v] = 1;
                arr[v][u] = 1;
            }
            bfs();
            System.out.println(result-1);
        }
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(1);
        visit[1] = true;
        while(!queue.isEmpty()) {
            result++;
            int val = queue.poll();
            for(int i=1; i<=N; i++) {
                if(arr[val][i]!=0 && !visit[i]) {
                    visit[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}