[백준 2644번] 촌수계산

www.acmicpc.net/problem/2644

2644번: 촌수계산

문제

 

출력

: 입력에서 요구한 두 사람의 촌수를 구하라. 촌수를 계산할 수 없을 때는 -1을 출력하라

 

예제

 

전체 사람 수  (1≤n≤100)	9
촌수를 구할 사람의 번호	7, 3
관계의 개수	7

관계

부모	자식
1	2
1	3
2	7
2	8
2	9
4	5
4	6

 

그래프를 이용하기 위해 위의 관계 입력값을 인접리스트 형식으로 받았습니다.

 

//vector<int> arr[101];

for (int i = 0; i < m; i++) {
	int s, e;
	cin >> s >> e;

	arr[s].push_back(e);
	arr[e].push_back(s);
}

 

 

 

 

입력받은 두 사람 사이의 촌수를 구하기 위해 DFS와 BFS 방식 중 최소값을 구할 수 있는 BFS를 사용하기로 했습니다.

 

int n, m;
int x, y;//촌수를 구할 사람의 번호

vector<int> arr[101];
bool check[101];
int dis[101];

void bfs(int x) {
	queue<int> que;
	que.push(x);
	check[x] = true;

	while (!que.empty()) {
		x = que.front();
		que.pop();
		
		for (int i = 0; i < arr[x].size(); i++) {
			int next = arr[x][i];
		
			if (check[next] == false ) {
				check[next] = true;
				que.push(next);
				dis[next] = dis[x] + 1; //최소거리를 구하기 위한 배열
				if (next == y) return; //x에서 시작하여 목표한 y에 도착했을 때
			}
		}
	}
}

 

 

전체 코드

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

using namespace std;

int n, m;
int x, y;

vector<int> arr[101];
bool check[101];
int dis[101];

int cnt = 0;

void bfs(int x) {
	queue<int> que;
	que.push(x);
	check[x] = true;

	while (!que.empty()) {
		x = que.front();
		que.pop();
		
		for (int i = 0; i < arr[x].size(); i++) {
			int next = arr[x][i];
		
			if (check[next] == false ) {
				check[next] = true;
				que.push(next);
				dis[next] = dis[x] + 1;
				if (next == y) return;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	cin >> x >> y;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int s, e;
		cin >> s >> e;

		arr[s].push_back(e);
		arr[e].push_back(s);
	}

	memset(check, false, sizeof(check));
	bfs(x); //x에서 bfs 시작


	if (dis[y] == 0) cout << -1; //촌수를 구할 수 없을 때
	else cout << dis[y]; // 목표한 y의 값 출력
	cout << "\n";

	return 0;
}