Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 9372 상근이의 여행
문제
상근이가 방학을 맞아 N개국을 돌아다닌다. 이때 가장 적은 종류의 비행기를 탈 수 있도록 도와주자! 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거치는 것도 가능하다.
입력 및 출력
첫 번째 줄: 국가의 수 a와 b쌍: a와 b를 왕복하는 비행기를 의미 주어지는 비행 스케줄은 항상 연결 그래프를 이룸
Spanning Tree: 최소 비용 신장 트리
- 그래프 내의 모든 정점을 포함하는 트리
- 트리의 특수 형태로 모든 정점들이 연결되어 있어야 하며 이 때 사이클을 포함해서는 안된다.
- 따라서 spanning tree는 n개의 정점을 정확히 n-1개의 간선으로 연결하게 된다.
- DFS나 BFS 탐색 중 사용된 간선만 모으면 만들 수 있다
spanning tree 알고리즘
depth_first_search(v):
v 방문 표시;
for all (v에 인접한 정점):
is 정점이 방문 전이라면
(v,u)를 간선을 표시;
depth_first_search(u)
코드
