Programmers > 코딩테스트 연습 > DFS/BFS > 네트워크

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43162

풀이

DFS/BFS 중 어떤 방법을 써서 풀어도 상관없는 문제이다.

일단 computers 벡터에 들어있는 수들을 처리하기 쉽게 다시 벡터함수에 저장하였다.

for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (computers[i][j] == 1) {
				v[i].push_back(j);
				v[j].push_back(i);
			}
		}
	}

이와같이 처리하였는데 이렇게 처리했을 때 노드별로 이어져 있는 노드들만 저장이 된다.

예를들어 1번노드가 2,3번 노드와 연결돼있다면

v[1][0] = 2 , v[2][0] = 1

v[1][1] = 3 , v[3][0] = 1

이런식으로 들어가는 것이다.

이렇게 초기화를 해준 후 DFS함수를 이용해 이어져 있는것은 모두 bool형식의 배열을 통해 check

하도록 하였으며

dfs함수가 돌아간다는 것은 한 네트워크를 모두 탐색한다는 것을 의미하므로

처음 dfs함수에 진입할 때마다 count++하여 총 네트워크의 수를 구하였다.

#include 
#include 

using namespace std;

bool check[200];
vector<int> v[200];

void dfs(int start)
{
	check[start] = 1;
	for (int i = 0; i < v[start].size(); i++)
	{
		int next = v[start][i];
		if (!check[next])
			dfs(next);
	}
}
int solution(int n, vector> computers) {
	int count = 0;
	for (int i = 0; i < n;i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (computers[i][j] == 1) {
				v[i].push_back(j);
				v[j].push_back(i);
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (!check[i])
		{
			count++;
			dfs(i);
		}
	}

	return count;
}
int main()
{
	vector> computers{ {1,1,0},{1,1,0},{0,0,1} };
	cout << solution(3,computers) << '\n';
}