[백준] 2644 - 촌수계산 (C++) lv.2

c++ 개발 환경 세팅 떔에 더 오래걸림

 

- python에서는 bfs의 queue를 deque함수로 사용해서, 습관적으로 deque로 함수를 짰다

 

촌수 관계를 입력받으면, 각 node에 어떤 사람과 가족인지 집어넣어주는데,

단방향이 그래프가 아니라 양방향 그래프기 때문에(서로 가족) edge를 c->d d->c 양쪽 다 넣어줘야 한다

 

그리고, q를 만들어서 전형적인 bfs 탐색을 시작하는데,

이때 visited 함수가 단순히 bool 함수로 방문 T/F를 처리하는게 아니라

현재 가족이 시작점(사람 a)으로부터 몇 번째 촌수인지 저장하기 위해

다음노드 = 현재노드+1 로 촌수를 누적 기록해준다

 

그리고 종료점(사람 b)가 되면 탐색을 멈추고

결과적으로 visited[b]를 출력하면 a->b 사이 촌수가 된다.

 

#include <iostream>
#include <deque>
#include <vector>
#include <set>
using namespace std;
int main() {
    int n=0;
    cin>>n;
    //N+1 길이의 배열 0으로 초기화
    vector<set<int>> arr(n+1);

    int a,b;
    cin >> a >> b;

    int m;

    cin >> m;
    for(int i=0;i<m;i++){
        int c,d;
        cin >> c >> d;
        arr[c].insert(d);
        arr[d].insert(c);
    }

    // BFS setup
    deque<int> queue;
    vector<int> visited(n + 1, -1);
    visited[a]=0;
    int ans=0;

    queue.push_back(a);
    while (!queue.empty()) {
        int current = queue.front();
        queue.pop_front();
        

        for (int neighbor : arr[current]) {
            if (visited[neighbor]==-1) {
                visited[neighbor] = visited[current]+1;
                queue.push_back(neighbor);

                if (neighbor==b){
                    cout << visited[neighbor]<<endl;
                    return 0;
                }
            }
        }
    }

    cout << -1 << endl;
    return 0;
}

 

근데 gpt랑 물어보면서 풀다보니

c++에서는 deque를 안쓰고 queue를 써도

deque의 pop_left(python3)같은 기능을 제공하는 것을 알게 되었다

 

queue.pop_front();를 하면 맨 왼쪽 요소가 튀어나오고

queue.push_back();을 하면 맨 마지막에 요소가 추가되어서 

FIFO 구조를 지원한다

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;

    int personA, personB;
    cin >> personA >> personB;

    int m;
    cin >> m;

    // 그래프 생성 (인접 리스트)
    vector<vector<int>> relations(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        relations[x].push_back(y);
        relations[y].push_back(x);  // 양방향 연결
    }

    // BFS 준비
    vector<int> visited(n + 1, -1); // -1로 초기화하여 방문 여부와 촌수 저장
    queue<int> q;

    // 시작 노드 설정
    q.push(personA);
    visited[personA] = 0;

    // BFS 탐색
    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int neighbor : relations[current]) {
            if (visited[neighbor] == -1) { // 방문하지 않은 노드만 탐색
                visited[neighbor] = visited[current] + 1; // 촌수 증가
                q.push(neighbor);

                // 목표 노드에 도달하면 촌수 출력 후 종료
                if (neighbor == personB) {
                    cout << visited[neighbor] << endl;
                    return 0;
                }
            }
        }
    }

    // 목표 노드에 도달할 수 없는 경우 -1 출력
    cout << -1 << endl;
    return 0;
}