C++ - (프로그래머스) BFS/DFS 네트워크

1. idea

- 각 노드를 시작점으로 하는 모든 경로 경우의 수를 따져봐야하는 문제이다.

- 방문했던 노드는 0 으로 만들어주어 체크해준다.

- 다른 그룹에 속하는지 확인하기 위해 solution함수에 for문으로 각 노드를 처음 시작점으로 dfs탐색 시작할 수 있게 해주고

- dfs함수를 만들어주어 재귀를 통해 각 노드를 연결시키며 각 그룹안에 경로를 완성시킨다.

#include <string>
#include <vector>
using namespace std;

vector<vector<int>> computers_network;

bool dfs(int n) {
	if (!computers_network[n][n]) return false;
	computers_network[n][n] = 0;

	for (int i = 0; i < computers_network.size(); i++) {
		if (computers_network[n][i]) dfs(i);
	}
	return true;
}

int solution(int n, vector<vector<int>> computers) {

	int answer = 0;
	computers_network = computers;
	for (int i = 0; i < n; i++) {
		if (computers[i][i] && dfs(i))answer++;
	}
	return answer;
}