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

백준 온라인 저지(BOJ) 24445번 알고리즘 수업 - 너비 우선 탐색 2

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

24445번: 알고리즘 수업 - 너비 우선 탐색 2

* 사용언어 : C언어, C++

 

1. 문제

graph 를 BFS(너비 우선 탐색)으로 탐색할 때

1번 정점부터 N번 정점까지 방문한 순서를 출력

(인접 정점은 내림차순으로 방문)

 

2. 풀이

앞서 풀어본 24444번 문제와 거의 유사한 코드로 구현하였습니다.

https://rightbellboy.tistory.com/244

[백준/BOJ] 24444번 알고리즘 수업 - 너비 우선 탐색 1 (C/C++)

 

다른 점은 vector 를 sort 할 때 내림차순으로 처리하기 위해

begin, end 대신 rbegin, rend 함수를 사용했다는 점 입니다.

 

그 외에는 동일하니 추가 설명 없이 마치겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24445_알고리즘 수업 - 너비 우선 탐색 2
7916KB	116ms
*/
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int LM = 100001;
vector<int> graph[LM];
int visited[LM], seq = 1;
int que[LM], fr, re;


void bfs(int r) {
	visited[r] = seq++;
	que[re++] = r; // enqueue

	int u;
	while (fr < re) {
		u = que[fr++]; // dequeue
		for (int i = 0; i < graph[u].size(); ++i) {
			if (!visited[graph[u][i]]) {
				visited[graph[u][i]] = seq++;
				que[re++] = graph[u][i]; // enqueue
			}
		}
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, s, u, v;
	scanf("%d %d %d", &n, &m, &s);

	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		if (u != s) graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) sort(graph[i].rbegin(), graph[i].rend());
	bfs(s);

	for (int i = 1; i <= n; i++) printf("%d\n", visited[i]);
	return 0;
}