[BOJ/C++] 5567 결혼식

문제

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

풀이

이 문제는 depth를 이용하기 때문에 BFS를 이용하면 효율적인데 나는 그냥 DFS로 품,,
DFS는 모든 경우를 탐색하기 때문에 check 배열을 통해 재귀여부를 파악하는데
이 문제는 방문했던 노드도 중복해서 방문하지만 특정 depth가 되면 재귀를 종료하도록 로직을 짜야함

🥊DFS vs BFS 선택 기준
대부분 둘 다 사용해도 무방

DFS
모든 경우를 하나하나 다 탐색해야 할 경우
ex) 순열, 조합

BFS
depth 특징을 활용해야 하는 문제
ex) 최단경로

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[501];
bool check[501];
int depth;

void dfs(int node, int depth) {
	if (depth > 2)	return;
	
	check[node] = true;

	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];

		dfs(next, depth+1);
	}
}

int main() {
	int n, m;
	int ans = 0;
	cin >> n >> m;

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

		v[a].push_back(b);
		v[b].push_back(a);
	}

	dfs(1,0);
	
	for (int i = 1; i <= n; i++) {
		if (check[i] == true)	ans++;
	}
	cout << ans - 1;
}