문제
접근 방법
전형적인 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; }