2644 촌수 계산

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

2644번: 촌수계산

 

(풀이)

문제 접근

1. 인접리스트를 이용한 BFS

 

2. 기본적인 인접리스트를 이용한 BFS를 구현할 수 있는지 묻는 문제 vector<vector<int>> v 로

2차원 연결리스트를 만들고, 해당 노드와 연결된 부분을 입력과 함께 연결시켜줌.

 

3. 시작점부터 도착지점을 찾을때까지 너비우선탐색, DFS로도 풀리는 문제이다.

 

4. 못찾으면 -1출력.

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N; //Node Count;
int from, to;
bool check[101];
void bfs(int Start_Node, vector<vector<int>> &v);
int list_count;
queue<pair<int,int>> q;
int main(void)
{
	cin >> N;
	vector<vector<int>> v(N+1);
	cin >> from >> to;
	cin >> list_count;
	
	int input_a, input_b;
	for (int i = 0; i < list_count; ++i)
	{
		cin >> input_a >> input_b;
		v[input_a].push_back(input_b);
		v[input_b].push_back(input_a);
	}
	 
	
	q.push(make_pair(from,0));
	check[from] = true;
	bfs(from,v);
	return 0;
}
void bfs(int Start_Node, vector<vector<int>> &v)
{
	while (!q.empty())
	{
		int node = q.front().first;
		int dist = q.front().second;
		if (node == to)
		{
			cout << dist << '\n';
			return;
		}
		q.pop();
		for (int i = 0; i < v[node].size(); ++i)
		{
			int next_node = v[node][i];
			if (check[next_node] == false)
			{
				check[next_node] = true;
				q.push(make_pair(next_node, dist + 1));
			}
		}
	}
	cout << -1 << '\n';
	return;
}