백준[2644] - 촌수계산

문제

백준 2644 문제 보기

접근 방법

전형적인 bfs 완전 탐색으로 문제를 해결할 수 있다.

각 가족들의 촌수를 양방향 그래프로 벡터에 저장한 뒤, 시작 노드부터 완전 탐색을 시작한다.

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 구조체 작성
struct info {
// 촌수를 카운트
int rel_cnt;
// 나의 노드
int my_num;
};
int n, r1, r2, cnt;
vector<vector<int>> rel(101);
int visited[101];
queue q;
int main() {
cin >> n;
cin >> r1 >> r2;
cin >> cnt;
for(int i = 0; i < cnt; i ++) {
int x, y;
cin >> x >> y;
// 촌수에 대한 양방향 그래프
rel[x].push_back(y);
rel[y].push_back(x);
}
// 나를 시작으로 완전탐색 시작
q.push({0, r1});
// 방문 체크
visited[r1] = 1;
while(!q.empty()) {
int rel_cnt = q.front().rel_cnt;
int my_num = q.front().my_num;
q.pop();
// 도착지점
if(my_num == r2) {
cout << rel_cnt;
return 0;
}
// 연결된 노드(가족)를 모두 검색
for(int i = 0; i < rel[my_num].size(); i ++) {
int next_rel = rel[my_num][i];
// 방문하지 않은 가족이 있다면
if(visited[next_rel] != 1) {
visited[next_rel] = 1;
q.push({rel_cnt + 1, next_rel});
}
}
}
cout << -1;
return 0;
}
Share