[C++] 백준 온라인 저지 2644번 촌수계산 풀이

친척 간 촌수가 몇 인지 구하는 문제

 

---

 

문제의 조건

 

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

 

입력

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

 

출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

 

 

풀이 과정

 

 양방향 그래프를 만든 뒤 촌수를 계산해야 하는 사람들 중 첫번째 번호 노드로 들어간 후 DFS로 부모를 찾아 거슬러 올라가면 될 것이라 생각하고 풀었습니다. 이걸 백트래킹이라고 하나요? 웬일로 구글링 없이 풀어서 좋네유~

 

1. 2차원 벡터를 만들어서 입력 받으면서 양방향 그래프를 만든다. 정답 초기값은 -1로 설정한다. 

 

2. start 노드부터 탐색을 시작해서 target을 찾는 dfs 함수를 만든다.(매개변수: 2차원 벡터, start, target, 촌수) start 노드와 연결된 노드 중 탐색하지 않은 곳이라면 재귀 호출을 해서 해당 노드로 들어가는데 이 때 촌수를 1 증가시킨다.

 

3. target 노드를 찾으면 현재 카운트 + 1 값을 정답으로 저장하고 dfs 함수를 빠져나온다. 

 

4. 정답을 출력한다. dfs함수에서 target을 찾았으면 정답이 -1 보다 큰 수일 것이고 찾지 못했으면 초기값인 -1 그대로일 것이다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int answer = -1; //dfs에서 target을 찾지 못하면 이거 그대로 출력 
vector<bool> visited;
void dfs(vector<vector<int>>& relationship, int start, int target, int count)
{
    //현재 정점(start)과 연결된 정점만 확인한다.
    for (int i = 0; relationship[start].size() > i; i++)
    {
        if (target == relationship[start][i])
        {
            //현재 노드와 연결된 노드 중 target이 있으면 촌수를 구할 수 있다. 
            //부모자식간은 1촌이기 때문에 현재 촌수에 1을 더해줘야 최종 정답이 된다. 
            answer = count + 1;
            return;
        }
        else 
        {
            //연결된 노드가 target이 아니고 방문하지 않았다면 탐색한다. 
            if (!visited[relationship[start][i]])
            {
                visited[relationship[start][i]] = true;
                dfs(relationship, relationship[start][i], target, count + 1);
            }
        }
    }
}

int main()
{
    int people;
    cin >> people;
    
    visited.assign(people + 1, false);
    
    int personA, personB;
    cin >> personA >> personB;
    
    int m;
    cin >> m;
    
    vector<vector<int>> relationship(people + 1);
    for (int i = 0; m > i; i++)
    {
        int a, b;
        cin >> a >> b;
        relationship[a].emplace_back(b);
        relationship[b].emplace_back(a);
    }
    
    visited[personA] = true;
    dfs(relationship, personA, personB, 0);
    
    cout << answer;
    
    return 0;
}