백준 9372 상근이의 여행(Java)

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

9372번: 상근이의 여행

---

 

해석 및 팁

 

---

 

이 문제는 이해만 하면 아주 쉬운 문제입니다. 가장 중요한 것은 문제에서 원하는 값은 모든 국가를 여행하기 위해 필요한 최소 비행기 종류의 개수라는 점입니다. 예를 들어 3개의 국가를 여행한다고 하면 최소의 경로는 1 -> 2 -> 3 이므로 2개가 필요합니다. 5개라고 하면 1 -> 2 -> 3 -> 4 -> 5 이므로 4개가 필요합니다. 따라서 (국가의개수-1)를 출력해 주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int t = sc.nextInt();
  
    for(int i = 0; i < t; i++) {
      int n = sc.nextInt();
      int m = sc.nextInt();
      int[][] arr = new int[n+1][n+1];
      for(int j = 0; j < m; j++) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        arr[a][b] = 1;
        arr[b][a] = 1;
      }
      sb.append(n-1).append("\n");
    }
    
    System.out.println(sb);
  }
}