C++ / 백준 / 2644 / 촌수계산

문제

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

 

문제풀이

DFS보다 BFS로 푸는 것이 좋아 보여서 BFS로 풀었다.

단순히 큐에 각 노드 번호와 촌수를 넣고 연결된 노드를 모두 큐에 넣었으면,

다음으로 넘어가고 이전 노드를 pop 하여 큐에서 삭제하는 방식이다.

큐가 비어있지 않은 상태로 원하는 노드에 도착하면 촌수를 return 하여 촌수를 출력하고,

큐가 비게 되어 반복문이 종료되면 노드가 연결되어있지 않아 촌수를 계산할 수 없으므로 -1을 return 하여 출력한다.

예제

4, 5, 6은 7과 연결되지 않으므로 무시해도 되는 트리이다.

7과 3의 촌수 계산 문제이므로 7부터 시작하여 3에 도착하면 반복문을 종료하고 계산한 촌수를 출력하면 된다.

한 번 방문한 곳은 재방문하지 않기 위해 bool형 vist벡터를 사용한다.

현재 노드가 7과 몇 번째로 연결되어있는지 구분하기 위해 pair을 이용했다.

queue의 형태는 {번호, 촌수}이다.

함수 인자를 최대한 적게 넣고 싶어서 배열을 전역으로 선언하여 main문에서 resize를 통해 입력받은 크기만큼 사이즈를 지정했다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
vector<vector<int>>relation;
vector<bool>visit;

int start;
int arrive;

int Bfs() {
    queue<pair<int, int>> q;
    q.push({ start,0 });
    while (!q.empty()) {
        int x = q.front().first;
        int answer = q.front().second;
        visit[x] = true;
        if (x == arrive)
            return answer;
        q.pop();
        for (int cnt = 0; cnt < relation[x].size(); ++cnt) {
            if(!visit[relation[x][cnt]])
            q.push({ relation[x][cnt],answer + 1 });
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n = 0;
    int num = 0;
    cin >> n;
    cin >> start >> arrive;
    cin >> num;

    relation.resize(n + 1, vector<int>(0, 0));
    visit.resize(n + 1, false);

    for (int i = 0; i < num; ++i) {
        int n1 = 0;
        int n2 = 0;
        cin >> n1 >> n2;
        relation[n1].push_back(n2);
        relation[n2].push_back(n1);
        visit[n1] = visit[n2] = false;
    }

    cout << Bfs();
}