[c/c++] 백준 24444 (Silver 2)

🔨 문제

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

<요약>
알고리즘 수업 - 너비 우선 탐색 1
간선 연결 후 오름차순 정렬하고 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());	//오름차순 정렬
	}
	
	bfs(start);	// bfs 시작 노드
	for (int i = 1; i <= n; i++) {
		cout << isVisited[i] << '\n';
	}
		
	return 0;
}