백준 2644번 촌수계산

문제 링크입니다: https://www.acmicpc.net/problem/2644

BFS(Breadth First Search) 알고리즘을 사용하여 푼 문제였습니다.

이번 문제는 visited 대신 cache를 이용하여 촌수가 이미 정해져있는 사람은 찾지 않고 촌수가 정해져있지 않은 사람만 큐에 넣어 계산하는 문제였습니다.

주의할 점은 부모 자식 관계를 벡터에 넣을 때 양방향으로 넣어줘야한다는 점입니다!

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

const int MAX = 100 + 1;

 

int N, M;

int node1, node2; //촌수 계산하는 두 사람

vector<int> family[MAX];

int cache[MAX];

 

//전형적인 BFS

int BFS(void)

{

        queue<int> q;

        q.push(node1);

       

        while (!q.empty())

        {

                 int currentNode = q.front();

                 q.pop();

 

                 if (currentNode == node2)

                         return cache[node2];

 

                 for (int i = 0; i < family[currentNode].size(); i++)

                 {

                         int next = family[currentNode][i];

                         //서로 촌수가 정해져있지 않았을 경우에만 update

                         if (cache[next] == 0)

                         {

                                 q.push(next);

                                 cache[next] = cache[currentNode] + 1;

                         }

                 }

        }

        return -1;

}

 

int main(void)

{

        cin >> N;

 

        cin >> node1 >> node2;

       

        cin >> M;

        for (int i = 0; i < M; i++)

        {

                 int parent, child;

                 cin >> parent >> child;

 

                 family[parent].push_back(child);

                 family[child].push_back(parent);

        }

 

        cout << BFS() << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~