[C++] 백준 - 2644 : 촌수계산

문제 링크

2644번: 촌수계산

 

풀이 ) BFS

  부모 자식 관계를 배열로 나타냈다. 이 때 행, 열의 구분은 중요하지 않다.

  입력으로 들어온 촌 수를 구하고자 하는 사람 중 한명을 큐에 먼저 넣는다. 촌수를 구하기 위해 촌수를 구분하기 위해 구분자 역할을 하는 0을 넣어주었다.

  입력으로 들어온 두 사람의 촌 수가 존재한다면 그 방향성은 중요하지 않기 때문에 큐에 넣고 빼는 동작을 하는 과정에서는 답이 증가하기만 한다.

  과정을 반복하는 중 큐가 비었을 때, 즉 딜리미터인 0이 연속으로 있는 경우는 촌수관계가 없기 때문에 -1을 출력한다.

 

#include <cstdio>
#include <queue>
using namespace std;

int n, in[2], m, child, parent, rel[101][101], visited[101], ans;
queue<int> q;

void bfs(int curr);

int main(void)
{
  scanf("%d", &n);
  scanf("%d%d", in, in+1);
  scanf("%d", &m);
  for(int i = 0; i < m; ++i){
    scanf("%d%d", &child, &parent);
    rel[child][parent]++;
    rel[parent][child]++;
  }
  bfs(in[0]);
  printf("%d\n", ans);
}

void bfs(int curr)
{
  visited[curr]++;
  q.push(curr);
  q.push(0);
  while(1){
    int next = q.front();
    if(next == in[1])
      return;
    if(next == 0){
      q.pop();
      if(q.front() == 0){
        ans = -1;
        return;
      }
      q.push(0);
      ans++;
      continue;
    }
    q.pop();
    for(int i = 1; i <= n; ++i)
      if(rel[next][i] && !visited[i]){
        visited[i]++;
        q.push(i);
      }
  }
}