[백준] 촌수계산(2644번) - C++

문제

입력

출력

소스 코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> v[102];
queue<int> q;
int visited[102];
int dist[102];

void bfs(int cur) {
	q.push(cur);
	visited[cur] = 1;
	while(!q.empty()) {
		for(int i=0;i<v[q.front()].size();i++) {
			if(visited[v[q.front()][i]] == 0) {
				q.push(v[q.front()][i]);
				visited[v[q.front()][i]] = 1;
				dist[v[q.front()][i]] = dist[q.front()] + 1;
			}
		}
		q.pop();
	}
}

int main() {
	int n; cin >> n;
	int p1, p2; cin >> p1 >> p2;
	int m; cin >> m;
	for(int i=0;i<m;i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	bfs(p1);
	if(dist[p2] != 0) {
		cout << dist[p2];
	}
	else cout << -1;
	return 0;
}

해당 문제는 BFS(너비 우선 탐색) 알고리즘을 이용하여 해결할 수 있었습니다.