백준 2644번 촌수계산 C++

출처 : https://www.acmicpc.net/problem/2644

 

bfs를 이용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, a, b, m, x, y;
	cin >> n;
	cin >> a >> b;
	vector<vector<int>> graph(n + 1, vector<int>());
	vector<bool> found(n + 1, false);
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	queue<pair<int, int>> q;
	q.push({ a,0 });
	found[a] = true;
	int ans = -1;
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		if (curr.first == b) {
			ans = curr.second;
			break;
		}
		for (auto next : graph[curr.first]) {
			if (found[next]) continue;
			found[next] = true;
			q.push({ next,curr.second + 1 });
		}
	}
	cout << ans;
};