https://www.acmicpc.net/problem/24445
<요약>
알고리즘 수업 - 너비 우선 탐색 2
간선 연결 후 내림차순 정렬하고 bfs이용하여 방문 순서 구하기
주석 ㄱㄱ
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<vector<int>> graph; //인접 리스트
//이중 vector 를 사용함으로써 필요한 메모리만 할당해서 사용할 수 있음
vector<int> isVisited; //정점 방문 여부 원래는 보통 bool형으로 확인만 하지만 여기서는 int형으로 저장
queue <int> q;
int cnt = 0;
void bfs(int cur){
q.push(cur);
isVisited[cur] = ++cnt;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < graph[cur].size(); i++) {
int next = graph[cur][i];
if (isVisited[next] == 0) {
q.push(next);
isVisited[next] = ++cnt;
}
}
}
}
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int n, line, start; //정점의 개수, 간선의 개수, 시작점 입력
cin >> n >> line >>start;
graph.assign(n + 1, vector<int>(0, 0)); //assign 함수를 통해서 vector<int>를 n+1개 할당
isVisited.assign(n + 1, 0); // 노드는 1~n, 모두 0으로 초기화
for (int i = 0; i < line; i++) { //간선 연결
int n1, n2;
cin >> n1 >> n2;
graph[n1].push_back(n2);
graph[n2].push_back(n1);
}
for (int i = 1; i <= n; i++) {
sort(graph[i].begin(), graph[i].end(),greater<>()); // 내림차순 정렬
}
bfs(start); // bfs 시작 노드
for (int i = 1; i <= n; i++) {
cout << isVisited[i] << '\n';
}
return 0;
}