[G4] 백준 4803번 트리 C++ BFS, 트리, 싸이클

리뷰

 

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

싸이클이 발생했다는 것에 대한 재정의를 하게 된 문제

 

 

전역 변수

1. n : 노드의 개수를 저장할 변수
2. m : 간선의 개수를 저장할 변수
3. ans : 트리의 개수를 저장할 변수
4. v : 각 노드의 방문 처리를 하기 위한 정수형 배열 

 

함수

1. bfs

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

 

너비 우선 탐색을 통해 싸이클 존재 여부를 판단하기 위한 함수

1. 매개 변수로 시작 노드와 인접 리스트를 전달 받는다.
2. 정수형 타입 큐 q를 초기화 하고 시작 노드를 큐에 삽입해 준다.
3. 시작 노드를 1로 방문처리 해주고, 트리 여부를 판단할 bool 형식의 변수 isTree를 true로 초기화 한다.
4. 큐가 빌 때 까지 탐색을 진행하고 큐의 제일 앞에 있는 노드를 꺼내 cn으로 초기화 한다.
5. cn의 인접 리스트를 순회하며 각 노드에 대한 방문 처리를 진행하고 큐에 삽입해 준다.
6. 만약 이미 방문한 노드일 경우 해당 노드가 cn의 부모 노드가 아니라면 isTree를 false로 변경해 준다.
7. 모든 탐색을 마치고 최종적으로 isTree의 값을 리턴해 준다.

 

2. solve

void solve()

 

간선 정보를 입력 받아 인접 리스트를 초기화 하고 모든 노드를 탐색하는 함수

1. 정수형 2차 벡터 lst를 n + 1크기로 초기화 해준다.
2. m개의 간선 정보를 입력 받아 양방향 간선으로 추가해 준다.
3. ans를 0으로 초기화 하고 n개의 노드를 순회한다.
4. 만약 해당 노드가 이미 방문처리 되어 있다면 continue 처리해 준다.
5. 만약 방문하지 않았따면 bfs를 수행하고, 리턴 값이 true라면 ans를 증가시켜 준다.

 

문제풀이

1. 정답을 저장하고 출력하기 위한 문자열 벡터 result를 초기화 해준다.
2. 정답 출력 시 각 케이스를 인덱싱 하기 위한 정수형 변수 cases를 0으로 초기화 해준다.
3. cases를 전위 증가 시키고 무한 루프를 실행해 준다.
4. n, m값을 입력 받고 만약 둘 다 0일 경우 break 처리하여 반복문을 빠져 나온다.
5. memset 메서드를 통해 이전 케이스에서 사용한 방문 배열을 0으로 초기화 해준다.
6. solve 함수를 통해 모든 노드를 탐색하며 트리의 개수를 ans에 저장해 준다.
7. 문자열 temp에 ans의 개수에 따라 현재 케이스의 정답을 저장해 준다.
8. result벡터에 temp를 추가해 준다.
9. 반복문이 끝났을 경우 result에 저장된 문자열을 출력해 준다.

 

참고 사항

간선을 양방향으로 추가하였으므로, 방문한 노드를 만났을 때 부모 자식 관계인지 체크가 필요하다.

 

 

정답 코드

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

int n, m, ans;
int v[501];

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

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

void solve() {
	vector<vector<int>> lst(n + 1);
	while (m--) {
		int par, child; cin >> par >> child;
		lst[par].push_back(child);
		lst[child].push_back(par);
	}

	ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (v[i]) continue;
		if (bfs(i, lst)) ans++;
	}
}

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

	vector<string> result;
	int cases = 0;
	while (++cases) {
		cin >> n >> m;
		if (!n && !m) break;

		memset(v, 0, sizeof(v));
		solve();

		string temp = "Case " + to_string(cases) + ": ";
		if (ans > 1) temp += "A forest of " + to_string(ans) + " trees.\n";
		else if (ans == 1) temp += "There is one tree.\n";
		else temp += "No trees.\n";

		result.push_back(temp);
	}
	for (const string& r : result) cout << r;
}