[JAVA]백준 9372: 상근이의 여행

백준 9372: 상근이의 여행

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

풀이

• 그래프 이론을 이용한 MST 구하기

첫번째 풀이

• bfs를 이용하여 풀어보려고 했음.
• 각 비행기 정보를 boolean 배열에 저장하고 탐색
• 시간초과

두번째 풀이

• 검색으로 찾아봤음.
• 이 문제에서 중요한 것은
  • 비행기의 개수가 아닌 종류를 구하는 것.
  • 간선의 가중치 X
  • 항상 연결 그래프
• mst의 간선의 개수 최솟값은 (노드의 개수 -1)
• 탐색하지 않고 N-1만을 출력하면 됨. 허허

---

Issue

• 세상에..