[백준] 24446번 알고리즘 수업 - 너비 우선 탐색 3

문제: 24446번: 알고리즘 수업 - 너비 우선 탐색 3

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>

using namespace std;

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

	int n, m, r; // 정점의 수, 간선의 수, 시작 정점
	cin >> n >> m >> r;

	// 0번 인덱스 안 써
	vector<vector<int>> nodes = vector<vector<int>>(n + 1);
	vector<int> dists = vector<int>(n + 1, -1);
	vector<int> visits = vector<int>(n + 1, 0);

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;

		// 무방향 그래프
		nodes[u].push_back(v);
		nodes[v].push_back(u);
	}

	queue<pair<int, int>> nexts;
	int start = r;
	nexts.push({start, 0});
	visits[start] = 1;
	while (!nexts.empty()) {
		pair<int, int> cur = nexts.front(); nexts.pop();
		dists[cur.first] = cur.second;

		for (int next : nodes[cur.first]) {
			if (visits[next] == 1) continue;

			nexts.push({ next, cur.second + 1 });
			visits[next] = 1; // 방문 표시!
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dists[i] << "\n";
	}

	return 0;
}

 

그냥 그래프에 BFS 적용하면 쉽게 해결할 수 있는 문제다.