취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24445번 문제인 알고리즘 수업 - 너비 우선 탐색 2이다.
문제는 아래 링크를 확인하자.

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

각 노드를 BFS순으로 이동하면서 방문한 순서를 출력하는 문제이다.

지금까지 방문 순서로 부여된 정수가 무엇인지를 하나의 변수를 이용해 기록해두면 이 작업을 간단히 할 수 있다.

노드번호를 내림차순으로 방문하는 것은 내림차순 정렬을 이용해 해낼 수 있다. 이는 sort함수를 이용해 정렬할 때 greater 구조체를 인자로 넘기는 것으로 간단하게 구현할 수 있다.

아래는 제출한 소스코드이다.

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

int N, M, R;
vector<int> G[100001];
bool visited[100001];
int ans[100001];
int ansval;

void bfs() {
	queue<int> que;
	que.push(R);
	visited[R] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		ans[cur] = ++ansval;
		for (auto& nxt : G[cur]) {
			if (visited[nxt]) continue;
			visited[nxt] = 1;
			que.push(nxt);
		}
	}
}

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

	cin >> N >> M >> R;
	while (M--) {
		int u, v; cin >> u >> v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}

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

	bfs();

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