[고득점Kit][DFS] 네트워크 ⭐⭐⭐

[DFS] 네트워크

난이도 ⭐⭐⭐

문제

각 원소는 아래와 같은 의미를 가진다.

• 첫 번째 원소인 [1, 1, 0]는 첫 번째 원소의 연결 상태를 나타낸다.
  • 자기 자신인 첫 번째 원소와 연결
  • 두 번째 원소와 연결
  • 세 번째 원소와는 연결 X

내 풀이 ⭕

DFS 초보라 어려웠지만 풀었다. 👏👏

#include <string>
#include <vector>

using namespace std;

void DFS(vector<vector<int>>& computers, vector<bool>& visited, int computer)
{
	if (computer == computers.size())
		return;

	for (int i = 0; i < computers.size(); i++)
	{
		if (computers[computer][i] == 1 && !visited[i])
		{
			visited[i] = true;
			DFS(computers, visited, i);
		}
	}
}

int solution(int n, vector<vector<int>> computers) {
	int answer = 0;
	vector<bool> visited(n);

	for (int i = 0; i < computers.size(); i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			DFS(computers, visited, i);
			answer++;
		}
	}

	return answer;
}

for 문을 통해 모든 정점들을 차례대로 DFS 를 다 해보되, 방문할 때마다 체크해서 방문 안된 경우에만 DFS 를 진행하도록 한다.

computer는 재귀 단계를 나타냄과 동시에 현재 살펴보고 있는 정점이다. if (computers[computer][i] == 1 && !visited[i]) 현재 살펴보고 있는 정점의 연결되어 있는 and 방문하지 않은 정점이 있다면 그 정점으로 또 깊숙이 들어간다. 물론 방문 체크 하고!

DFS 는 BFS와 함께 그래프의 모든 노드를 순회하는 방법 中 하나라는 것을 기억하자.

DFS(computers, visited, i); 하나의 DFS 과정이 전부 끝났다면 전부 이어져 있는 하나의 네트워크(그래프이자 그룹)를 전부 탐색 완료한 것이다! 따라서 이렇게 해당 정점을 탐색 시작점으로 하는 DFS 탐색이 완료 되면 answer를 1 증가시키면 된다. 방문 체크를 하기 때문에 앞으로도 방문 안된 정점들에 대해서만 DFS 를 진행하며 새로운 네트워크(그래프)를 찾게 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기