[C/C++ 백준 2644번] 촌수계산 (Silver 2)

www.acmicpc.net/problem/2644

2644번: 촌수계산

bfs를 사용하는 문제. 그냥 찾는게 아니라, 깊이를 따져서 해당 숫자가 깊이 몇에 있는지 따져가며 탐색 해야한다. 그 부분만 주의하고 알고 있으면 풀 수 있다.

 

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n, x, y, t, a, b;
int depth[101];
void bfs(int start, vector <int> graph[], bool check[]){
	depth[start] = 0;
	bool stop = false;
	queue<int> q;
	q.push(start);
	check[start] = true;
	while(!q.empty()){
		int temp = q.front();
		q.pop(); 
		for(int i=0; i<graph[temp].size(); i++){
			if(graph[temp][i]==y)
				stop = true;
			if(check[graph[temp][i]]==false){
				q.push(graph[temp][i]);
				check[graph[temp][i]] = true;
				depth[graph[temp][i]] = depth[temp] + 1;
			}
		}
	}
	if(!stop)
		printf("-1");
	else
		printf("%d",depth[y]);
}
int main(void){
	scanf("%d", &n);
	vector<int> graph[n+1];
	bool check[n+1];
	fill(check, check+n+1, false);
	scanf("%d %d", &x, &y);
	scanf("%d", &t);
	for(int i=0; i<t; i++){
		scanf("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	bfs(x, graph, check);
}