백준 9372_상근이의 여행 문제풀이 in C++

2022년 11월 17일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

백준 : 9372_상근이의 여행

문제 요구사항

---

• 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,
• 각 테스트 케이스마다 다음과 같은 정보가 주어진다.
• 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
• 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b)
• 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.
• 테스트 케이스마다 한 줄을 출력한다.
• 상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.

접근 방법

---

• 입력받은 연결 그래프 정보 a, b를 벡터에 넣고 해당 벡터를 탐색하며, 비용을 계산하도록 풀이하였다.
• 위 방법으로 오답처리를 받고 자세히 보니, 결국엔 N - 1만큼이 최소 값이 되게 된다….

풀이 순서

---

1. test_case를 입력받아 해당 test_case 크기만큼 반복하며 진행한다.
2. N과 M을 입력받아 M만큼 반복하여 a와 b를 입력 받는다.
3. N -1을 출력하며 test_case 반복

소스코드

---

#include <iostream>

using namespace std;

int N, M, test_case;

void input() {
	cin >> test_case;

	for (int tc = 0; tc < test_case; tc++) {
		cin >> N >> M;

		for (int i = 0; i < M; i++) {
			int a, b;
			cin >> a >> b;
		}

		cout << N - 1 << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();

	return 0;
}

문제 풀이 결과

---