9372번: 상근이의 여행
첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가
www.acmicpc.net
<내 코드>
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
for _ in range(M):
a, b = map(int, input().split())
print(N-1)일단 문제에서 모든 곳이 연결된 그래프이기 때문에, 최소 비행기 수는 (나라 수 - 1)이다. 왜냐하면 모든 나라를 여행하는 것이라 시작점을 어디든지 될 수 있다. 즉, 한중일 세 나라가 있다면 한국 - 일본, 한국 - 중국 이런식으로 시작점을 맘대로 정할 수 있기 때문이다.
반응형
'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글
| [백준 2644] 촌수계산 - Python(그래프 탐색, BFS) (0) | 2020.10.08 |
|---|---|
| [백준 2263] 트리의 순회 - Python (트리, 재귀) (1) | 2020.10.07 |
| [백준 1967] 트리의 지름 - Python (트리, DFS) (0) | 2020.10.04 |
| [백준 11725] 트리 부모 찾기 - Python (DFS, 트리) (0) | 2020.10.03 |
| [백준 1991] 트리 순회 - Python (트리, 재귀) (0) | 2020.10.03 |