BaekJoon 5567 결혼식

Link https://www.acmicpc.net/problem/5567

소스결과 2112 KB / 4 ms

출처 baekjoon, JOI 2010

언어 C++ 17

분류 그래프 이론

 

설명

상근이가 결혼식에 학교 동기 중 자신의 친구와, 친구의 친구를 초대할 때 상근이가 초대할 친구의 수를 구하는 문제이다.

 

동기의 수가 최대 500명이기 때문에 인접리스트를 써도 무방하다.

또한 a - b가 친구이면 b - a도 친구라는 점에서 양방향 그래프로 추가 하면 된다.

상근이를 기준으로 깊이가 2 이하인 친구들의 수를 출력하면 된다.

동기의 수만큼 배열을 만들어 깊이를 저장하는 방법도 있고 깊이가 2까지 진행 하게 DFS를 진행하는 방법도 있다.

 

아래 소스코드는 두 방법이 아닌 큐를 이용해서 친구를 구한 후 친구의 친구를 구하는 방법으로 상당히 단순 무식하게 만들었다.

가끔은 이런 일탈도 괜찮지 않을까

 

알고리즘

1. 인접 행렬을 구성할 간선들을 받는다.

2. 0(1) 번을 기준으로 깊이가 1인 친구들을 Queue에 넣는다.

3. Queue에서 한개씩 꺼내어 중복 체크를 하며 친구의 수를 1씩 늘린다.

4. 출력한다.

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

const unsigned short MAX = 500;

int main()
{
	bool adj[MAX + 1][MAX + 1] = {};
	bool check[MAX + 1] = { true, };
	int n, m, inviteCount = 0;
	queue<int> q;
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;

		adj[x - 1][y - 1] = adj[y - 1][x - 1] = true;
	}

	for (int i = 0; i < n; i++)
		if (adj[0][i] && !check[i])
		{
			check[i] = true;
			inviteCount++;
			q.push(i);
		}

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		for (int i = 0; i < n ; i++)
			if (!check[i] && adj[cur][i])
			{
				check[i] = true;
				inviteCount++;
			}
	}

	cout << inviteCount;

	return 0;
}