[백준] 5567번. 결혼식

[백준] 5567번. 결혼식

1. 문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.

3. 출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

4. 풀이

• BFS로 풀었다. 깊이가 1인 친구와 2인 친구의 수를 찾는 문제였다.
• 큐에 1과 연결된 모든 노드를 삽입하고 방문 처리, while문을 시작해 큐에 든 노드와 연결된 모든 노드를 방문 처리하여 방문한 노드의 개수를 모두 세주었다.
• BFS 단계가 정해져 있어서 다시 큐에 넣는 동작은 처음에만 수행하면 된다.

5. 처음 코드와 달라진 점

• friend의 철자를 틀렸다..ㅎ
• count를 할 때 자기 자신도 세주었다. loop 시작을 1에서 2로 바꾸었다.
• 단방향 연결에서 양방향 연결로 바꾸어주었다.

6. 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> graph[501];
bool visited[501];
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;
	int m;
	cin >> m;

	for (int i = 0; i < m; i++){
		int from, to;
		cin >> from >> to;
		graph[from].push_back(to);
	}

	queue<int> q;
	for (int i = 0; i < graph[1].size(); i++){
		int first_friend = graph[1][i];
		q.push(first_friend);
		visited[first_friend] = true;
	}

	while (!q.empty()){
		int x = q.front();
		q.pop();
		for (int i = 0; i < graph[x].size(); i++){
			int y = graph[x][i];
			if (!visited[y]) visited[y] = true;
		}
	}

	int numberOfFriends = 0;
	for (int i = 2; i <= n; i++){
		if (visited[i]) numberOfFriends++;
	}

	cout << numberOfFriends;
	

}