https://www.acmicpc.net/problem/2644
2644호: 합동 계산
개인 1, 2, 3, … , n(1 ≤ n ≤ 100)은 각각 연속된 숫자로 표시됩니다. 입력 파일의 첫 번째 줄은 총 인원수 n을 가져오고 두 번째 줄은 학위를 계산할 서로 다른 두 사람의 수를 가져옵니다.
www.acmicpc.net
#include <iostream>
#include <vector>
#include <algorithm>4
#include <queue>
constexpr int unvisited = 0;
constexpr int visited = 1;
using namespace std;
// 촌수문제 -> 그래프 형식 but, 부모는 하나이기 때문에 트리 형태로 구성된다.
// 또한 누가 부모인지 상관없이 두 노드 간의 촌수만 구하면 되기 때문에
// 한 정점에서부터 dfs를 수행하면 된다. -> dfs도 가능할 것이지만 bfs가 더 효율적일거 같다.
// bfs로 구현
int main() {
int n;
cin >> n;
vector<vector<int>> tree(n + 1);
vector<bool> isvisited(n + 1, unvisited);
pair<int, int> relationNum; // par, child 관계로 노드 번호가 주어진다.
int a, b;
cin >> a >> b;
relationNum.first = a;
relationNum.second = b;
int edgecnt;
cin >> edgecnt;
while (edgecnt--) {
cin >> a >> b;
tree(a).push_back(b);
tree(b).push_back(a);
}
// while문이 끝난 후에 7, 3중 하나에 대해서 bfs를 수행하는게 더 좋을거 같다.
queue<pair<int, int>> q;
q.push(make_pair(relationNum.first, 0)); // 큐에는 relationNum.first를 넣을 것이다.
isvisited(relationNum.first) = visited;
/*bool isnode = 0;*/
int cntc, nodenum;
while (!q.empty()) {
nodenum = q.front().first;
cntc = q.front().second;
for (int i = 0; i < tree(nodenum).size(); i++) {
if (nodenum == relationNum.second) {
cout << cntc << '\n';
return 0;
/*isnode = 1;
break;*/
}
if (isvisited(tree(nodenum)(i)) == unvisited) {
q.push(make_pair(tree(nodenum)(i), cntc + 1));
isvisited(tree(nodenum)(i)) = visited;
}
}
q.pop();
}
/*if (cnt == 0) */
cout << -1 << '\n';
}
노드 번호가 두 개인 경우 해당 노드가 연결되어 있는지 + 연결된 경우 몇 도인지 파악하는 것이 문제입니다.
노드 번호가 주어지면 두 노드 중 하나에서만 dfs를 실행하여 해결할 수 있습니다.
연결되어 있으면 0이 반환됩니다. cout 직후, 명령문이 실행되지 않은 경우 끝에 cout << -1.