[BOJ] 24445번_알고리즘 수업 - 너비 우선 탐색 2_BFS (C++)

[문제]

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

주어진 의사코드를 활용해서 BFS함수를 만들면 되는 문제이다.

[사용 알고리즘]

BFS(너비 우선 탐색), 정렬

[풀이 핵심]

• 내림차순으로 정점을 방문해야되는 조건이 있으므로 입력받은 노드를 algorithm헤더의 sort함수를 통해 내림차순으로 정렬한다. (내림차순 정렬을 위한 compare함수 생성)
• BFS를 돌면서 정점을 몇 번째로 방문했는지 알아야 되므로 정점을 방문할 때마다 cnt를 1씩 늘려주며 저장해준다.

  문제의 예제에선 R이 1이므로 1->4->2->3순으로 진행된다.
  따라서 1의 cnt는 1, 4의 cnt는 2, 2의 cnt는 3, 3의 cnt는 4가 된다. 그래서 예제의 출력은 1 3 4 2 0이 되는 것이다.

[코드]

//boj24445번_알고리즘 수업 - 너비 우선 탐색 1_그래프

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

vector<int> graph[100001];
bool visited[100001];
int result[100001];
int cnt = 0;

bool compare(int x, int y) {
	return x > y;
}

void BFS(int V) {
	visited[V] = true;
	queue<int> q;
	q.push(V);
	cnt++;
	result[V] = cnt;

	while (!q.empty()) {
		V = q.front();
		q.pop();

		for (int i = 0; i < graph[V].size(); i++) {
			int num = graph[V][i];

			if (!visited[num]) {
				visited[num] = true;
				cnt++;
				result[num] = cnt;

				q.push(num);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, R;
	cin >> N >> M >> R;

	for (int i = 0; i < M; i++) {
		int V1, V2;
		cin >> V1 >> V2;

		graph[V1].push_back(V2);
		graph[V2].push_back(V1);
	}

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

	BFS(R);

	for (int i = 1; i <= N; i++) {
		cout << result[i] << '\n';
	}
}