[백준 2644] 촌수 계산

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

---

해설

전형적인 BFS 문제라 해설할 건 따로 없고 그냥 BFS 돌려주면 된다.

 

처음에 서로 다른 두 사람의 번호를 입력받고

i) 두 사람의 번호가 같으면 자기 자신이니 0 출력

ii) 두 사람 중 한명의 좌표를 BFS 돌려서 큐에 들어간 값이 다른 사람의 좌표와 같아지면 카운트 출력하고 프로그램 종료.

iii) 두 사람이 연결되어있다면 while 문안에서 프로그램이 종료된다.

하지만 만약에 while 문 내에서 프로그램이 끝나지 않고 끝까지 가면 두 사람은 서로 연결되어있지 않은 것이니 마지막에 -1 출력하나 놔둔다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){
	int n, x, y, m; cin >> n >> x >> y >> m;
	vector<int> v[101];
	bool visited[101];
	for(int i=0; i<m; i++){
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	if(x==y){
		cout << 0 << '\n';
		return 0;
	}
	using p = pair<int, int>;
	queue<p> q;
	q.push({x, 0});
	while(!q.empty()){
		p f = q.front();
		if(f.first == y){
			cout << f.second << '\n';
			return 0;
		}
		q.pop();
		for(int k =0; k<v[f.first].size(); k++){
			if(!visited[v[f.first][k]]){
				visited[v[f.first][k]] = true;
				q.push({v[f.first][k],  f.second + 1});
			}
		}
	}
	cout << "-1" << '\n';
}