[백준] 9372 상근이의 여행 - Java

 

 

 

문제 출저

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

9372번: 상근이의 여행

 

 

 

문제 풀이

테스트케이스 t가 주어집니다. t만큼 주어진 문제를 풀어야 합니다.

문제는 나라의 개수 n개가 주어집니다. 그리고 항공편이 k개 주어집니다. 모든 나라를 탐색할 수 있는 항공편의 최소 개수를 구해야 합니다.

 

이 문제는 최소 신장 트리(MST)문제입니다.

최소 신장 트리의 특징은 간선의 갯수는 (정점의 갯수-1) 입니다. 

그러므로 정답은 n-1로 쉽게 구할 수 있습니다.

 

저는 BFS를 이용해서 문제를 풀었습니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
상근이의 여행
https://www.acmicpc.net/problem/9372

블로그 글을 통해 알아보니 더 쉬운 방법이 있었다.
간선의 개수는 (정점의 개수 - 1) 이다.
그러므로 정답은 n-1 이다. ㅋㅋ
 */

public class Main {

  static int t;
  static int n; // 국가의 갯수
  static int m; // 비행기의 종류
  static List<Integer>[] flights;

  static StringBuilder sb;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    t = Integer.parseInt(br.readLine());

    sb = new StringBuilder();

    while(t-->0) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());
      m = Integer.parseInt(st.nextToken());

      flights = new List[n+1];
      for(int i = 0; i < n+1; i++) {
        flights[i] = new ArrayList<>();
      }

      for(int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        flights[s].add(e);
        flights[e].add(s);
      }

      solution();
    }

    System.out.println(sb.toString());

  }

  // 비행기 최소 종류 구하기
  // 비행기를 몇 번 타는게 아니라 비행기 종류를 구해야 한다.
  // BFS로 구했다.
  public static void solution() {

    int answer = 0;

    // 1부터 시작
    boolean[] visited = new boolean[n + 1];
    visited[1] = true;

    Queue<Integer> que = new LinkedList<>();
    que.add(1);

    while (!que.isEmpty()) {
      Integer s = que.poll();
      for(int number : flights[s]) {
        if(!visited[number]) {
          answer++;
          que.add(number);
          visited[number] = true;
        }
      }
    }

    sb.append(answer).append("\n");

  }

}