반응형
문제
https://www.acmicpc.net/problem/9372
9372번: 상근이의 여행
첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가
www.acmicpc.net
풀이
약간 넌센스? 같은 문제입니다.
비행 스케줄은 항상 연결 그래프이기 떄문에, n개국을 여행하기 위한 최소의 경로는 n - 1 개입니다.
소스코드
후기
최소 스패닝 트리로 분류되어 있어서, 간선의 비용을 모두 1로 하고 제거해봐야 했는데.. 그럴필요가 없는 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 4386 별자리 만들기 (Swift) (1) | 2023.05.17 |
|---|---|
| [BOJ] 백준 1197 최소 스패닝 트리 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 20040 사이클 게임 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 4195 친구 네트워크 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 1976 여행 가자 (Swift) (0) | 2023.05.16 |
