C++ 백준 5567 결혼식

백준 5567

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

5567번: 결혼식

풀이 전 나의 생각

상근이의 친구와 친구의 친구를 결혼식에 초대하기로 했을 때,

동기들의 친구 리스트를 기준으로 초대할 사람의 수를 구해야한다.

 

조건

- n (2 ≤ n ≤ 500)

- m (1 ≤ m ≤ 10000)

- (1 ≤ ai < bi ≤ n)

 

과정

상근이의 동기 친구 관계 리스트는 그래프 형태로 주어지기 때문에

그래프를 상근이의 친구, 친구의 친구까지 DFS나 BFS의 형태로 탐색해주면

해결되는 문제다.

 

1. 동기 친구 리스트의 정보를 저장한다.

for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;

		link[u].push_back(v);
		link[v].push_back(u);
	}

 

2. 친구의 친구까지 DFS를 이용하여 탐색을 진행한다.

void dfs(int now, int depth)
{
	if (depth == 2) return;

	for (int next : link[now])
	{
		visited[next] = true;
		dfs(next, depth + 1);
	}
}

친구, 친구의 친구까지라는 의미는 결국 노드의 자식과, 노드의 자식의 자식까지만 탐색한다는 의미기 때문에

상근이의 노드인 1에서 갈 수 있는 최대 깊이인 2까지 모두 방문표시를 해준다.

 

3. 상근이가 초대할 수 있는 최대 친구의 수를 구한다.

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

방문 표시가 됐다는 건 깊이 2까지 탐색된 노드들이라는 의미다.

따라서 친구와 친구의 친구라는 의미와 같기 때문에 이를 통해 최종값을 구해낼 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>> link(501);
bool visited[501];
int ans = 0;

void dfs(int now, int depth)
{
	if (depth == 2) return;

	for (int next : link[now])
	{
		visited[next] = true;
		dfs(next, depth + 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;

		link[u].push_back(v);
		link[v].push_back(u);
	}

	visited[1] = true;
	dfs(1, 0);

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

	cout << ans;
}