백준[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;
}