반응형
상근이의 여행
-
[백준] 9372 상근이의 여행 with PythonPS 2022. 2. 22. 20:17
📌 BOJ 9372 상근이의 여행 💡 조건 N개국을 여행할 상근이에게 가장 적은 비행기를 타고 여행할 수 있게 도와주자. 테스트 케이스의 수 T(T ≤ 100) 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다. 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b) 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 그래프이론, 유니온-파인드 유형의 문제 🖥 소스 코드 from sys import stdin def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, paren..