[C/C++] 백준 알고리즘 수업 - 너비 우선 탐색 문제 모음

✏️ 문제 링크

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

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

bfs를 구현하는 문제입니다. visited배열을 만들어서 각 정점의 방문 여부를 체크해주고, order배열을 만들어서

정점들의 방문 순서들을 저장해 주면 됩니다. 오름차순으로 인접 정점을 방문해줘야 하므로 sort 정렬을 해줍니다.

 

 

✏️ 문제 코드

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

int N, M, R;
vector<vector<int>>mlist;
bool visit[100001];
int order[100001];
int cnt = 1;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> R;
	mlist.resize(N + 1);

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		mlist[u].push_back(v);
		mlist[v].push_back(u);
	}

	for (int i = 1; i <= N; i++)
		sort(mlist[i].begin(), mlist[i].end());

	order[R] = cnt++;
	visit[R] = true;

	queue<int>q;
	q.push(R);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (int next : mlist[node]) {
			if (visit[next])
				continue;
			visit[next] = true;
			order[next] = cnt++;
			q.push(next);
		}
	}

	for (int i = 1; i <= N; i++)
		cout << order[i] << "\n";
}

 

 

 

✏️ 문제 링크

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

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

위에서 방금 보았던 문제와 동일하며 차이점으로는 인접 정점을 내림차순으로 방문해야 합니다.

각 정점들의 방문 정점들을 오름차순으로 정렬하고 bfs로 탐색 시 그래프의 마지막 부분에서부터 탐색을 하면 됩니다.

 

 

✏️ 문제 코드

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

int N, M, R;
vector<vector<int>>mlist;
bool visit[100001];
int order[100001];
int cnt = 1;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> R;
	mlist.resize(N + 1);

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		mlist[u].push_back(v);
		mlist[v].push_back(u);
	}

	for (int i = 1; i <= N; i++)
		sort(mlist[i].begin(), mlist[i].end());

	order[R] = cnt++;
	visit[R] = true;

	queue<int>q;
	q.push(R);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for(int i=mlist[node].size()-1;i>=0;i--){
			int next = mlist[node][i];
			if (visit[next])
				continue;
			visit[next] = true;
			order[next] = cnt++;
			q.push(next);
		}
	}

	for (int i = 1; i <= N; i++)
		cout << order[i] << "\n";
}

 

 

 

✏️ 문제 링크

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

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

bfs로 탐색을 하면서 depth배열에 각 정점들의 깊이를 저장하면 됩니다.

depth배열에 저장할 때는 depth[방문할 정점] = depth[현재 노드] + 1로 저장하시면 됩니다.

인접 정점을 오름차순으로 접근해야 하므로 각 그래프에 대해서 sort정렬을 해주어야 합니다.

 

✏️ 문제 코드

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

int N, M, R;
vector<vector<int>>mlist;
bool visit[100001];
int depth[100001];
int cnt = 1;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> R;
	mlist.resize(N + 1);

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		mlist[u].push_back(v);
		mlist[v].push_back(u);
	}

	for (int i = 1; i <= N; i++) {
		sort(mlist[i].begin(), mlist[i].end());
		depth[i] = -1;
	}

	depth[R] = 0;
	visit[R] = true;

	queue<int>q;
	q.push(R);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for(int next:mlist[node]){
			if (visit[next])
				continue;
			visit[next] = true;
			depth[next] = depth[node] + 1;
			q.push(next);
		}
	}

	for (int i = 1; i <= N; i++)
		cout << depth[i] << "\n";
}

 

 

 

✏️ 문제 링크

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

 

✏️ 문제 설명

✏️ 문제 풀이

위에서 접근했던 문제들을 모두 합쳐서 푸는 문제입니다. depth배열에 깊이를 저장하고 order배열에 방문 순서를 저장합니다. 그 다음 res에 각 정점들의 방문 순서와 깊이를 곱해서 더해줍니다. int형으로 하게 되면 오버플로우가 발생하기 때문에

long long형을 사용해 줍니다

 

 

✏️ 문제 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long

int N, M, R;
vector<vector<int>>mlist;
bool visit[100001];
ll depth[100001];
ll order[100001];
ll cnt = 1;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> R;
	mlist.resize(N + 1);

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		mlist[u].push_back(v);
		mlist[v].push_back(u);
	}

	for (int i = 1; i <= N; i++) {
		sort(mlist[i].begin(), mlist[i].end());
		depth[i] = -1;
	}

	depth[R] = 0;
	visit[R] = true;
	order[R] = cnt++;

	queue<int>q;
	q.push(R);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for(int next:mlist[node]){
			if (visit[next])
				continue;
			visit[next] = true;
			depth[next] = depth[node] + 1;
			order[next] = cnt++;
			q.push(next);
		}
	}

	ll res = 0;
	for (int i = 1; i <= N; i++) {
		ll mul = order[i] * depth[i];
		res += mul;
	}
	cout << res;
}