[백준 5567] 결혼식

www.acmicpc.net/problem/5567

5567번: 결혼식

트리를 레벨별로 순회하는 문제로 생각하면 된다.

root =1 로 잡고 레벨 2가 되는 지점까지 연결된 노드수를 구한다.

 

1. 입력시 양방향 그래프 구현을 위해 벡터를 사용한다.

2. 루트노드인 1을 큐에 넣고 순회를 시작한다.

3. 레벨별 순회이므로 큐 사이즈만큼 순회한다.

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
int n, m;
vector<int> v[501];
bool visited[501];
int main(void)
{
  scanf("%d%d", &n, &m);

  for (int i = 0; i < m; i++)
  {
    int a, b;
    scanf("%d%d", &a, &b);
    v[a].push_back(b);
    v[b].push_back(a);
  }

  visited[1] = true;
  queue<int> q;
  q.push(1);

  int level = 0;
  int res = 0;
  while (!q.empty())
  {
    int sze = q.size();
    level++;

    if (level == 3)
    {
      break;
    }
    for (int i = 0; i < sze; i++)
    {
      int cur = q.front();
      q.pop();

      for (int j = 0; j < v[cur].size(); j++)
      {
        if (visited[v[cur][j]])
          continue;
        q.push(v[cur][j]);
        visited[v[cur][j]] = true;
        res++;
      }
    }
  }

  printf("%d\n", res);
  return 0;
}