[ 백준 2644 ] 촌수계산 (C++)

백준의 촌수계산(2644)문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 문제의 입력으로 전체 사람의 수와, 촌수를 계산해야 하는 2사람의 번호, 그리고 문제에서 주어진 특정 수만큼 부모와 자식

  관계를 가진 두 사람의 번호가 주어진다.

- 입력으로 받은, 부모와 자식 관계를 가진 두 사람은 서로 1촌이며, 이를 토대로 촌수를 알고 싶어하는 두 사람의 촌수를 도

  출해 내면 되는 문제이다.

- 어렵지 않은 BFS / DFS문제이며, DFS로 할 경우, 매개변수로 연결된 사람들을 계속해서 설정해주면서 호출해주면 쉽게

  구할 수 있을 것이고, BFS로 접근할 경우, 기존의 BFS에서 약간만 변형해서 구현한다면 어렵지 않은 문제이다.

  ( 본인은 BFS로 풀이 하였음 )

[ 문제풀이 ]

1. 먼저 입력으로 주어지는 부모와 관계 자식(1촌)을 갖는 사람들을 Vector에 넣어주었다.

   이 때, Vector에 양방향그래프 처럼 넣어주었다. 왜냐하면, 부모와 자식이 1촌이고, 자식과 부모도 1촌이기 때문이다.

   즉 Connect[Parent].push_back(child) & Connect[Child].push_back(Parent) 이런식으로 부모에게 접근하더라도

   자식에게 갈 수 있고, 자식에게 접근하더라도 부모에게 갈 수 있도록 값을 넣어 주었다.

   또한, 촌수를 계산해야 하는 두 사람 중 앞사람의 번호를 Start, 뒷사람의 번호를 End라는 변수를 만들어서 따로 관리해

   주었다.

2. BFS함수에서는 가장 먼저 Queue에 Start번호를 넣어주었으며 이 번호를 시작으로 반복을 시키되, 반복하다가 촌수를 계산

   해야 하는 두 사람 중 뒷 사람의 번호가 나오게 되면 그대로 종료시켜주었다.

3. 여기서 Start를 기준으로 촌수를 계산하는 배열 하나를 만들었다. Result[] 라는 배열을 사용해 주었는데, 이 Result 배열의

   의미는 Result[a] = b ==> Start와 a의 촌수는 b입니다. 라는 의미이다.

   3-1) 즉, 예를 들어서 Start가 1 End가 0이라고 가정해보자. 그리고 부모와 자식 관계를 입력으로 받을 때, 1 3 을 입력받게

         되면, Result[3] = 1이 되는 것이다. 왜냐하면 Result라는 것은 앞서 말했다 시피, Start점을 기준으로 몇 촌인지를

         나타내는 배열이고, 1과 3은 자식과 부모 관계로써 1촌이 되므로, Result[3] = 1이 된다.

4. BFS에서 기존의 문제들에서는 MAP을 입력받고 상하좌우로 움직이는 경우가 많이 있었는데, 이 문제 같은 경우 MAP이 

   존재하는 것이 아니기 때문에 구현 내용이 약간 달라진다. 

   본인 같은 경우에는, for(int i = 0 ; i < Command[x].size(); i++) 라는 반복문을 통해서 Start점으로부터 연결되어 있는 모

   든 점을 방문하면서, 아직 방문하지 않은 번호에 대해서는 +1 씩 시켜주었다.

   4-1) 예를 들어서 4)번을 설명하자면

         Start가 5이고 End가 6이라고 가정해보자. 5와 4 , 4와 6은 부모와 자식 관계라고 생각해보자.

         이렇게 되면 Connect[5]에는 4라는 값이 있을 것이고, Connect[4]에는 6이라는 값이 있을 것이다. 

         Start점인 5가 처음에 Queue에 들어가게 되고, BFS안에서 4라는 값을 꺼내올 것이다. 4는 아직 한번도 방문하지 않

         았으므로, Result[4] = 0일 것이고, 이 값을 Result[4] = Result[5] + 1 시켜주어, Result[4] = 1로 만들어 주었다.

         이후에, 4가 Queue에 들어갈 것이고, 4에서도 6을 꺼내올 것이다. Result[6] 은 아직 방문하지 않았기에 0일 것이고

         Result[6] = Result[4] + 1을 해서 2라는 값을 저장해주었다.

         즉, End라는 값을 만나게 되었으니, 종료시키고 Result[End] = Result[6] = 2를 출력시키는 방식으로 구현했다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 100
 
using namespace std;
 
int N, M, Start, End;
int Result[MAX];
bool Visit[MAX];
 
vector<int> Connect[MAX];
 
void Input()
{
    cin >> N;
    cin >> Start >> End;
    cin >> M;
    for (int i = 1; i <= M; i++)
    {
        int Child, Parent;
        cin >> Parent >> Child;
        Connect[Parent].push_back(Child);
        Connect[Child].push_back(Parent);
    }
}
 
int BFS()
{
    queue<int> Q;
    Q.push(Start);
 
    while (Q.empty() == 0)
    {
        int x = Q.front();
        Q.pop();
 
        if (x == End) return Result[x];
 
        for (int i = 0; i < Connect[x].size(); i++)
        {
            int nx = Connect[x].at(i);
            if (Result[nx] == 0)
            {
                Q.push(nx);
                Result[nx] = Result[x] + 1;
            }
        }
    }
    return -1;
}
 
void Solution()
{
    int Answer = BFS();
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}