🎭 촌수계산

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	25156	11851	8982	46.435%

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

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

입력

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

출력

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

예제 입력 1

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 출력 1

3

예제 입력 2

9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 출력 2

-1

🧨 풀이 과정

• 노드(부모)와 노드(자식)이 주어졌을 때, 사이의 연결 관계를 계산하는 문제
• 사이 사이에 노드가 몇 개 있는지(몇 촌인지) 계산하므로, 사실 거리 계산 문제
• 이러한 유형은 bfs 가 유리
• 보통 bfs 구현할 때 해당 노드 방문 여부를 파악하기 위한 bool 형 배열을 선언하여 사용하지만, 이번 문제의 경우 방문 여부와 더불어 거쳐온 거리를 계산하기 위해 int 형 배열로 선언하여 기록

🧵 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

  const int MAXI = 101;
  int node, a, b, edge; 
  vector<int> graph[MAXI]; // 노드 엣지 관계를 저장할 vector
  int memo[MAXI] = {0,}; // 거리를 저장할 배열 memo

int bfs(int start, int end) // 거리 계산은 bfs 가 유리
{
  queue<int> q; // bfs 는 큐로 구현함
  q.push(start); // start 를 앞에 넣고

  while(!q.empty()) // 큐가 빌때까지 반복할건데
  {
    int x = q.front(); // x 에 큐 맨 앞에 있는 애를 넣고
    q.pop(); // 걔를 없앰 POP

    if(x == end) return memo[x]; // 만약에 x 가 우리가 도달해야 하는 노드 end 이면, 해당 노드까지의 거리가 저장된 memo[end] 반환

    else // 노드 end 로 도달하지 못했다면
    {
      for(int i = 0 ; i < graph[x].size(); i ++) // 우리가 받은 x와 연결된 모든 관계를 조사할건데
      {
        int y = graph[x][i]; // 노드 번호가 작은순대로 할거고, y에 x와 연결된 노드 번호를 가까운 애부터 저장할것
        if(!memo[y]) //memo[y] 가 0이 아니라면 (하나이상 건너갔다면)
        {
          q.push(y); // y를 큐에 넣어주고
          memo[y] = memo[x] + 1; // 거리 하나 증가시켜줌
        }
      }
    }
  }
  return -1; // 큐가 빌떄까지 반복했는데 start가 end에 도달못하면 연결관계가 없는거니까 -1 반환
}

int main()
{

  cin >> node >> a >> b >> edge;

  for(int i = 0 ; i < edge ; i ++)
  {
    int Ainput, Binput;
    cin >> Ainput >> Binput;
    graph[Binput].push_back(Ainput);
    graph[Ainput].push_back(Binput);
  }  // 입력받기

  cout << bfs(a,b) << '\n';
  
  return 0;
}