[2644번] 촌수계산

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. BFS

그래프에서의 BFS문제이다.

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

    {

        int from, to;

        scanf("%d %d", &from, &to);

 

        vc[from].push_back(to);

        vc[to].push_back(from);

    }

위와 같이 그래프를 형성한다.

        pii get = q.front();

        int here = get.first;

        int cost = get.second;

here은 현재 번호(사람)를 의미한다.

cost는 촌수를 의미한다.

        if (here == end)

        {

            visit[here] = true;

            printf("%d", cost);

            break;

        }

현재 사람이 내가 원하던 사람이면

방문을 표시해주고

촌수를 표시해준다.

        for (int i = 0; i < vc[here].size(); i++)

        {

            int there = vc[here][i];

            if (visit[there])

                continue;

            q.push(pii(there, cost + 1));

        }

현재위치에 있는 사람과 바로 인접해있는 사람들을 push해주면서 촌수를 + 1해준다.

    if (!visit[end])

        printf("-1");

시작위치에서 출발하여 찾기를 원하던 위치에 도달하지 못하였을 경우, 두 사람의 친척 관계가 없다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

#include <iostream> #include <cstdio> #include <vector> #include <queue>   using namespace std;   typedef pair<int, int> pii;   vector<int> vc[101]; queue<pii> q; bool visit[101];   int main() {     int n;     int start, end;       scanf("%d", &n);     scanf("%d %d", &start, &end);       scanf("%d", &n);     for (int i = 0; i < n; i++)     {         int from, to;         scanf("%d %d", &from, &to);           vc[from].push_back(to);         vc[to].push_back(from);     }       q.push(pii(start,0));       while (!q.empty())     {         pii get = q.front();         int here = get.first;         int cost = get.second;           q.pop();           if (here == end)         {             visit[here] = true;             printf("%d", cost);             break;         }           if (visit[here])             continue;                  visit[here] = true;           for (int i = 0; i < vc[here].size(); i++)         {             int there = vc[here][i];             if (visit[there])                 continue;             q.push(pii(there, cost + 1));         }     }       if (!visit[end])         printf("-1");       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus