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

 

문제 24445번

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

 

어제 문제에서 오름차순이 내림차순으로 바뀌었다. 그래서 정렬을 해줄 때 greater<int>()를 추가해주면 내림차순으로 정렬할 수 있다.

 

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

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

void bfs(int r) {
	queue<int> q;
	q.push(r);
	visited[r] = true;
	cnt++;
	result[r] = cnt;
	while (!q.empty()) {
		int first = q.front();
		q.pop();
		for (int i = 0; i < graph[first].size(); i++) {
			int temp = graph[first][i];
			if (!visited[temp]) {
				q.push(temp);
				visited[temp] = true;
				cnt++;
				result[temp] = cnt;
			}
		}

	}
}

int main() {
	int n, m, r;
	cin >> n >> m >> r;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end(), greater<int>());	//내림차순
	}
	bfs(r);
	for (int i = 1; i <= n; i++) {
		cout << result[i] << '\n';
	}

	return 0;
}