🟦/백준
[실버 4] 상근이의 여행
진뚱이용
2023. 2. 16. 01:02
https://www.acmicpc.net/problem/9372
9372번: 상근이의 여행
첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가
www.acmicpc.net
풀기 전:
DFS로 모든 경우 순회하고 최소인 경로 값
풀이 중:
이거 dfs 어떻게 하더라 bfs 하다가 까먹었다
근데 2 -> 3 갔다가 다시 2로 돌아오는데 다른 종류의 비행기가 아니므로 카운트하지 않는다
그럼 결국 무조건 연결되어 있다고 했으므로 Node의 개수 -1 아닌가?
맞네