백준 9372. 상근이의 여행(JAVA)

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 Main {

    static int[][] arr;
    static boolean[] visit;
    static int T, N, M;
    static int result;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for(int i =0 ;i < T; i++){
        
            st = new StringTokenizer(br.readLine());
            
             N = Integer.parseInt(st.nextToken());
             M = Integer.parseInt(st.nextToken());
             
            arr = new int[N+1][N+1];
            visit = new boolean[N +1];
            
            for(int j = 0 ; j < M ; j++){
            
                st = new StringTokenizer(br.readLine());
                
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                
                arr[a][b] = arr[b][a] = 1;
                
            }
            System.out.println(bfs(1) -1 );
        }

    }

    static int bfs(int num){
    
        Queue<Integer> q = new LinkedList<>();
        q.add(num);
        visit[num] = true;
        result = 0;
        
        while(!q.isEmpty()){
        
            result++;
            int val = q.poll();
            
            for(int i = 1 ; i <= N ;i++){
            
                if(arr[val][i] == 1 && !visit[i]){
                
                    visit[i] = true;
                    q.add(i);
                    
                }
            }
        }
        return result;
    }
}

○ 문제 요약

상근이가 모든 나라를 여행하기 위해 최소 몇 번의 비행기를 타야 하는지 구해라.

 

○ 문제 풀이

먼저 큐에 1번 나라를 넣고 방문했다는 표시를 visit에 해당 인덱스에 맞게 true로 바꿔주자. 

 

현재 큐에는 1이 들어있기 때문에 while문 조건을 충족하여 while문을 수행하면

for문에서 i가 2일 때, 

if(arr[1][2] == 1 && !visit[2]){

 visit[2] = true;

 q.add(2);

}

를 수행하면서 큐에 2가 들어간다.

 

위에서 for문을 통해 큐에는 현재 2가 들어있고 while문을 수행하면 

for문에서 i가 3일 때, 

if(arr[2][3] == 1  && !visit[3]){

 visit[3] = true;

 q.add(3);

}

를 수행하면서 큐에 3이 들어간다. 다시 한번 while문을 실행하면 for문의 if문을 충족시키지 못하고 while문을 탈출하게 된다. 

 

그러면 result의 값이 반환되는데 여기서 result는 3이므로 bfs(1)의 값은 3이 된다.

하지만 우리가 구해야 하는 값은 N의 값이 아닌 N - 1이므로 bfs(1)을 해서 나온 값에 1을 뺀 값을 출력하면 된다.

 

○ 결과