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

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

프로그래머스

 

각 노드들이 연결되어있는지를 파악하고 한 묶음을 네트워크라 칭한다.

여기서 네트워크가 총 몇개인지? 출력하는 문제.

 

BFS로도 가능하다. 필자는 DFS로 풀었고, 

각 노드 별로 탐색을 하되, 한번 탐색을 했던 기록을 visited에 저장해서 더 이상 탐색하지 않도록 했다.

왜냐면 단 하나라도 연결이 되면 그 노드는 네트워크에 속하기 때문이다.

 

모든 노드와도 연결되지 않은 노드의 경우는 노드 하나만 있는 단일 네트워크이므로 그 부분을 세는 처리를 진행헸다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool visited[201];
vector<int> connected[201];
int n;


void DFS(int idx){
    
    //방문 처리 진행
    if(visited[idx] == false) visited[idx] = true;
    else return;
    
    
    //연결된 노드들을 확인
    for(int i = 0; i < connected[idx].size(); i++){
        
        //연결되어 있을 경우, 탐색
        DFS(connected[idx][i]);
    }

}

int solution(int _n, vector<vector<int>> computers) {
    
    // 1 <= n <= 200 자연수
    n = _n;
    int answer = 0;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            
            if(i == j) continue;
            
            if(computers[i][j] == 1) connected[i].push_back(j);
        }
    }
    
    //각 노드별 탐색을 진행한다
    for(int i = 0; i < n ; i++){
        
        
        //하나도 연결되어있지 않을 경우, 네트워크 하나로 취급
        if(connected[i].size() == 0){
            
            cout << "alone" << endl;
            answer++;
            continue;
        }
        
        
        //연결되어 있지만, 
        if(visited[i] == false) {
            
            cout << "탐색" << endl;
            
            DFS(i);
            answer++;
        }
    }
    
    return answer;
}

 

결과