[백준 2644/C++] 촌수계산

이진중·2022년 5월 30일
0

알고리즘

목록 보기
41/76

촌수계산


문제풀이

  1. 촌수를 계산하기위해 사람을 정점, 부모 자식관계를 간선으로 생각했다.
  2. 그래프 탐색은 가장 짧은 동선을 찾기 편한 BFS로 탐색을 진행했다.
  3. 노드를 한단계식 더 탐색해 나갈때마다 cnt를 한개씩 올렸고, 목적하는 노드가 나오면
    그 cnt를 ans에 저장했다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"

#define MAX 100+1
int n, m;
int target1, target2;
vector<int> graph[MAX];
bool visited[MAX];
int ans;
queue<int> q;


void bfs(int v,int cnt) {

	if (v==target2)
	{
		if (ans<=cnt)
		{
			ans = cnt;
		}
	}
	visited[v] = true;

	q.push(v);

	while (!q.empty()) {

		int w = q.front();
		q.pop();

		for (auto k : graph[w]) {

			if (!visited[k])
			{
				bfs(k,cnt+1);
			}
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> n;
	cin >> target1 >> target2;
	cin >> m;
	
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;

		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	bfs(target1, 0);

	if (ans==0)
	{
		cout << -1;
	}
	else {
		cout << ans;
	}
}

0개의 댓글