[C++][Programmers][DFS/BFS] 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

[해결방법]

연결된 네트워크 그룹개수를 찾는 것. DFS 로 탐색하며 count를 늘려주면 된다.

방문체크 배열은 따로 만들지 않고, 방문한 곳을 1 -> 0으로 바꿔주며 재탐색을 방지했다.

 

[알아둘 것]

1) DFS를 한 사이클 끝내고 돌아왔을 때, 컴퓨터의 최대 개수만큼은 DFS를 탐색해줘야 한다

최대 네트워크 수가 최대 컴퓨터 개수이기 때문이다.

 

2) DFS함수에 if(!computer[n][n]) return false; 를 안해주면 segementation 에러가 난다.

DFS 함수 호출 전에 solution 함수 if문에서 computers[i][i] != 0 구문을 적어줘도 DFS함수에 if(!computer[n][n]) return false; 를 안해주면 segementation 에러가 난다.

끽해봐야 computers[0][0], computers[1][1] computers[2][2] 일텐데 왜 segmentation 에러가 나는진 모르겠다...

 

[코드]

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


bool DFS(vector<vector<int>>& computers, int n){
    if (!computers[n][n]) return false;
    computers[n][n] = 0;
    
    for(int i = 0; i < computers[i].size(); i++){
       if(computers[n][i] == 1) DFS(computers, i);
    }
    return true;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i = 0; i < n; i++){
        if(DFS(computers, i)) answer++;
    }

    return answer;
}