#BOJ 2644カウント

🎭 カウント

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

質問する
わが国には独特の文化があり、家庭や親戚の関係を世代単位で表現している.これらの寸法は、次のように計算されます.基本的に親と子の間を一寸と定義し、人々の間の寸数を算出する.たとえば私とお父さん、お父さんとおじいさんはそれぞれ1寸で、おじいさんは2寸で、お父さんの兄弟とおじいさんは1寸で、私とお父さんの兄弟は3寸です.
親と子供の間に多くの人との関係を築くときは、与えられた2人の世代を計算するプログラムを作成してください.
入力
1、2、3、…、n(1≦n≦100)の連続番号として表される.入力ファイルの最初の行には整数nが与えられ、2番目の行には整数を計算する必要がある2つの異なる番号が与えられる.また,3行目は親子関係の個数mを与えた.4行目から、親子の関係を表す2つの番号x,yが各行に現れる.このとき、前の数字xは、後の整数yの親数字を表す.
一人当たり最大一人の両親しかいません.
しゅつりょく
入力に要求された2人のカウントを表す整数を出力します.場合によっては、親戚関係が全くなく、世代を計算できないこともあります.この場合、-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を実施する際にブールアレイを使用してノードにアクセスするか否かを決定するが、今回の問題では、アクセスするか否かおよび経過する距離を計算するために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;
}