[BOJ] 5567번_결혼식_DFS (C++)

[문제]

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

상근이의 친구와 친구의 친구까지 몇명인지 구하면 되는 문제이다.
당연히 친구의 친구의 친구는 안된다.
DFS를 사용해서 상근이에서 DFS의 깊이가 2일 때까지 진행후 들린 노드의 개수를 세어주거나
BFS를 사용해서 상근이로부터 거리가 2또는 3인 경우를 세어주면된다.
나는 DFS를 사용해서 해결했다.

[사용 알고리즘]

DFS(깊이 우선 탐색)

[풀이 핵심]

• 양방향 그래프이므로 입력받은 그래프를 양방향으로 저장한다.
• 1부터(상근이의 노드가 1) DFS를 돌면서 count를 늘려주고 count가 2가 되었을때 return해준다.
• DFS가 끝나면 들린 노드의 개수를 세어준다. (1은 상근이이므로 상근이를 제외하고 2부터 세어준다.)

[코드]

//boj5567번_결혼식_그래프

#include<iostream>

using namespace std;

int graph[501][501];
bool visited[501];

int n, m;

void DFS(int V, int count) {
	visited[V] = true;

	if (count == 2) {
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (graph[V][i] == 1) {
			visited[i] = true;
			DFS(i, count + 1);
		}
	}
}

int main() {
	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		graph[a][b] = 1;
		graph[b][a] = 1;
	}

	DFS(1, 0);

	int result = 0;

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

	cout << result;

	return 0;
}