프로그래머스 코테 연습 : 네트워크 [C++] DFS/BFS

DFS, BFS 두가지 방법으로 풀었다.

DFS와 BFS는 탐색 경로가 다른것 뿐이지 비슷하다.

 

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 200;

int answer = 0;
bool visited[MAX];

void dfs(vector<vector<int>> computers, int node){
    visited[node] = true;
    
    // 다른 노드들을 모두 체크
    for(int i = 0; i<computers.size(); i++){
        
        // 만약 현재노드와 연결된 노드이고 방문한적 없는 노드이면
        if(!visited[i] && computers[node][i]){
            // 재귀
            dfs(computers, i);
        }
    }
}

void bfs(vector<vector<int>> computers, int node){
    queue<int> q;
    q.push(node);
    
    while(!q.empty()){
        int front = q.front();
        q.pop();
        
        for(int i = 0; i < computers.size(); i++){
            if(!visited[i] && computers[front][i]){
                q.push(i);
                visited[i] = true;
            }
        }
    }
    
}

int solution(int n, vector<vector<int>> computers) {
    
    for(int i=0; i<n ; i++){
        // 방문되지 않은 노드이면 dfs 호출
        // dfs문에서 미리 불렸을수 있기 때문에 방문여부 체크 필요
        if(!visited[i]){
            // dfs
            // dfs(computers, i); // 노드와 연결된 노드들을 모두 돌고 나온다.
            
            // bfs
            bfs(computers, i);
            
            // 네트워크 수를 ++ 시킨다. 
            answer++;
        }
        
    }
    
    return answer; 
}