백준 알고리즘 2644번 - 촌수계산

전형적인 bfs를 이용해서 푸는 문제.

시간 복잡도 : bfs이고, 인접행렬로 구했으므로 o(n^2)

 

소스코드

 

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

using namespace std;

int connected[101][101]={0,};
bool visited[101]={false,};
int counts[101]={0,};
int p,rel,from,to;

void bfs(int start)
{
	
	visited[start]=1;
	queue<int> q;
	q.push(start);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=1;i<=p;i++){
			if(connected[now][i]==1 && !visited[i]){
				counts[i]=counts[now]+1;
				q.push(i);
				visited[i]=1;
			}
		}			
	}
}

int main() 
{
	cin>>p>>from>>to>>rel;
	for(int i=1;i<=rel;i++){
		int a,b;
		cin>>a>>b;
		connected[a][b]=1;
		connected[b][a]=1;
	}
	bfs(from);
	if(counts[to]==0) cout<<"-1";
	else cout<<counts[to];
}