문제
상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.
출력
첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.
예제 입력 1
6
5
1 2
1 3
3 4
2 3
4 5예제 출력 1
3예제 입력 2
6
5
2 3
3 4
4 5
5 6
2 5예제 출력 2
0노트
- 탐색 시작은 무조건 1번 정점부터 한다.
- 문제 상
친구의 친구까지. 즉, 1번 정점에서 상대 거리가 2 이하인 정점의 개수를 카운팅하면 될 것 같다.
구현
#include <iostream>
#include <queue>
#include <vector>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)
#define MAX 501
#define DEP_LIMIT 2
std::vector<int> V[MAX];
int dist[MAX];
int N, M;
int result = 0;
void BFS(int start) {
std::queue<int> Q;
dist[start] = 0;
Q.push(start);
while (!Q.empty()) {
auto cur = Q.front();
Q.pop();
for (auto next : V[cur]) {
if (dist[next] == -1) {
dist[next] = dist[cur] + 1;
if (dist[next] <= DEP_LIMIT) {
Q.push(next);
result++;
}
}
}
}
}
void solve() {
std::cin >> N;
std::cin >> M;
std::fill(dist, dist + MAX, -1);
int a, b;
for (int i = 0; i < M; i++) {
std::cin >> a >> b;
V[a].push_back(b);
V[b].push_back(a);
}
BFS(1);
std::cout << result;
}
int main() {
IO;
solve();
return 0;
}개선점
- 현재 BFS 코드는 문제 제약에 특화된 코드로 범용성이 떨어진다. 추후 확장성을 위해서는 BFS는 탐색만 하고, 집계는 따로 빼는게 나을 수도 있겠다.