<Programmers> DFS/BFS_네트워크 c++

문제링크

A와 B가 연결되어 있고, B와 C가 연결되어 있을 때 A-B-C 는 모두 같은 네트워크 상에 있다는 것만 보아도 각 과정에서 가능한 '깊이' 들어가려고 시도하고 있으니 DFS, 깊이 우선 탐색으로 풀어야 한다는 것을 알 수 있다.

1. 각 computer에 대한 인접 행렬은 vector<vector<int>> computers
   로 주어져 있다

e.g computers[0][1]==1라는 말은 1번 컴퓨터와 2번 컴퓨터가 연결되어 있다는 뜻

2. vector<bool> visited (n, false)
   visited[] 를 두고 참조하여 모든 정점을 순회한다.

3. DFS 함수는 current (현재 computer 번호), n (컴퓨터개수),computers를 파라메터로 두고 한 컴퓨터에 연결된 다른 컴퓨터가 있고, 그 다른 컴퓨터가 한 번도 방문된 적이 없을 때 DFS를 호출

     for (int i=0; i<n; i++) {
         int next=computers[current][i];
         if (next==1 && !visited[i]) 
             dfs(i, n, computers);
     } 

소스 코드

#include <string>
#include <vector>

using namespace std;
vector<bool> visited;

void dfs(int current, int n, vector<vector<int>>computers) {
  visited[current]=true;
 
  for (int i=0; i<n; i++) {
      int next=computers[current][i];
     
      if (next==1 && !visited[i]) 
          dfs(i, n, computers);
  }
}

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

  visited=vector<bool> (n, false);
 
  for (int i=0; i<n; i++) {
      if (!visited[i]) {
      dfs(i,n,computers);
      answer++;
      }
  }
  return answer;
}