[S4] 백준 9372번 상근이의 여행 C++ BFS

리뷰

 

https://www.acmicpc.net/problem/9372

문제 분류로 풀어보기에서 MST에 있길래 시도했으나 일반적인 BFS나 DFS로도 해결이 가능한 문제

 

 

전역 변수

• t : 테스트 케이스의 개수
• n : 국가의 개수
• m : 주어지는 인접 리스트의 개수
• v : 방문 처리용 정수형 배열

 

함수

1. bfs

int bfs(int sn, const vector<vector<int>>& lst)

 

너비 우선 탐색을 통해 방문한 간선의 최소 개수를 구하기 위한 문제

1. 매개변수로 시작 국가의 번호 sn과 인접 리스트 lst를 전달 받는다.
2. 정수형 타입 큐 q를 초기화 하고 sn을 큐에 삽입해 준다.
3. sn을 방문처리 해주고, 방문한 국가 cnt를 1로, 탑승한 비행기의 수 result를 0으로 초기화 한다.
4. q가 빌때 까지 반복문을 수행하고, 매 수행마다 큐의 제일 앞 국가 번호 cn를 꺼내준다.
5. cn의 인접리스트를 순회하며 이동 가능한 다음 국가 nn이 방문처리가 되어 있지 않다면 방문한다.
6. 방문한 후에는 nn에 방문 처리를 진행하고 cnt와 result를 증가시켜 준다.
7. 이후 q에 nn을 삽입해 준 뒤 탐색을 계속 진행해 준다.
8. 탐색이 완료되었을 경우 result를 리턴해 준다.

 

문제풀이

1. 테스트 케이스의 개수 t를 입력받은 후 t번의 반복문을 수행해 준다.
2. n, m값을 입력 받고 인접 리스트를 저장할 2차원 정수형 벡터 lst를 n + 1크기로 초기화 한다.
3. m개의 간선 정보를 받은 뒤 양방향 간선으로 lst에 추가해 준다.
4. memset 메서드를 통해 방문배열 v를 초기화 해준다.
5. bfs 함수에 시작 국가 1과 인접 리스트 lst를 매개 변수로 전달하여 리턴 값을 출력해 준다.

 

참고 사항

• 문제를 보니 "주어지는 비행 스케줄은 항상 연결 그래프를 이룬다." 라는 조건이 있다.
• 그렇다면 트리 형태가 가장 적은 간선을 사용하면서 모든 국가를 방문할 수 있는 형태이다.
• 트리의 간선은 정점의 개수보다 1만큼 작은 특성을 가진다.
• 따라서 노드의 개수 n에서 1만큼 뺀 값을 출력하면 무조건 정답이 될 것이다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

int t, n, m;
int v[1001];

int bfs(int sn, const vector<vector<int>>& lst) {
	queue<int> q;
	q.push(sn);
	v[sn] = 1;
	int cnt = 1;
	int result = 0;

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		for (int nn : lst[cn]) {
			if (v[nn]) continue;
			v[nn] = 1;
			cnt++;
			result++;
			q.push(nn);
		}
	}
	return result;
}

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

	cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;

		vector<vector<int>> lst(n + 1);
		while (m--) {
			int sn, dn; cin >> sn >> dn;
			lst[sn].push_back(dn);
			lst[dn].push_back(sn);
		}

		memset(v, 0, sizeof(v));
		cout << bfs(1, lst) << "\n";
	}
}

 

#include<iostream>
using namespace std;

int t, n, m;

int main() {
	cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;
		while (m--) {
			int sn, dn; cin >> sn >> dn;
		}
		cout << n - 1 << "\n";
	}
}