백준 2644 촌수계산(c++)

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

2644번: 촌수계산

<코드>

#include <iostream>
#include <queue>
#define max 101
using namespace std;
int a,b;
int board[max][max];
int x,y,n,m;
int visited[max] = {0};
int cnt[max] = {0};
void bfs(int node)
{
	
	queue<int>q;
	q.push(node);
	while(!q.empty()){
		node = q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			
			if(board[node][i] && !visited[i])
			{
				q.push(i);
				visited[i] = true;
				cnt[i] = cnt[node]+1;
			}
		}
	}
}
int main()
{
	cin>>n;
	cin>>x>>y;
	cin>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		board[a][b] = board[b][a] = 1;		
	}
	bfs(x);
	
	if(!cnt[y]){
	cout<<-1;
	return 0;
	}
	cout<<cnt[y];
}

<풀이과정>

bfs로 접근해서 풀었다. start(시작 정점) , end(마지막 정점)을 의미한다. 

큐에 시작 정점을 push하고 시작정점과 연결된 부분을 찾아서 개수를 하나 증가시켜주면 된다.

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

다음 테스트케이스를 보면

7(부모노드) 2 1 3(자식노드) 순서로 촌수가 3임을 확인할 수 있다.