[BOJ/C++] 2644(촌수계산)

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

1. 촌수 계산 - 가계도 생각하면 LCA일 것이라고 생각
2. 상하 관계 없이 촌수만 계산하면 됨 -> BFS로 충분히 풀 수 있을 것으로 판단됨

• 상하 관계로 주어지는 이유로, 벡터 배열에서는 간단하게 연결된 관계처럼 만들었습니다.
• 연결된 관계가 되는 순간 2차원 배열상의 BFS로 간단하게 해결할 수 있습니다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define p pair<int, int>

int n, m, st, en, answer = 101;
vector<int> a[101];
bool vis[101];

void input() {
	cin >> n >> st >> en >> m;
	int x, y;
	for (int i = 0; i < m; ++i) {
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
}

void solution() {
	input();
	queue<p> q;
	q.push(make_pair(st, 0));
	while (!q.empty()) {
		p cur = q.front(); q.pop();
		if (vis[cur.first]) continue;
		vis[cur.first] = 1;
		if (cur.first == en && answer > cur.second) {
			answer = cur.second;
			continue;
		}
		for (auto i : a[cur.first]) {
			if (vis[i]) continue;
			q.push(make_pair(i, cur.second + 1));
		}
		for (auto i : a[cur.first]) {
			if (vis[i]) continue;
			q.push(make_pair(i, cur.second + 1));
		}
	}
	if (answer == 101) {
		cout << -1;
		return;
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}