백준 9372번: 상근이의 여행 - 최소 신장 트리 성질 이용

 

최소 신장 트리(minimum spanning tree)를 이용하는 문제이다. 한 가지 기억해두어야 할 최소 신장 트리의 특징은 

"" 간선의 개수 = 정점의 개수 - 1 "" => 즉, "" 비행기 종류의 최소 개수 = 국가수 - 1 ""

 

따라서 이 문제는 "입력된 N값 - 1"이 답이다.

 

백준 단계별 문제풀이에서 '최소 신장 트리' 부분에 있어서 그 성질을 떠올릴 수 있었다. 저번학기 (3-1) 에 알고리즘 수업을 들은 것이 참 도움이 많이 되었다는 생각이 들었다.

 

그 성질만 이용하면 답은 바로 나오기 때문에 '어떻게 답을 구하지?' 보다는 '어떻게 입력값을 받을까?'에 더 초점을 두게 되었다. 항상 Scanner와 System.out.println() 을 이용하여 입출력을 했었는데 요즘에는 보다 효율적인 코드를 위해

 

1. Scanner 대신 BufferedReader 를 사용

2. StringBuilder 를 사용

3. 동시에 StringTokenizer 를 사용

 

을 습관하기 위해 노력하고 있다. 아직 헷갈리는 부분이 있지만 하나씩 이해하고 암기하며 배워가야겠다.

 

그리고 한 가지 더, 

int t = Integer.parseInt(rd.readLine());

BufferedReader 를 사용하여 입력 받기 위해서는 꼭 IOException 을 해당함수와, 그 함수를 호출하는 함수 모두에 꼭 달아줘야 한다는 사실도 기억하자.