프로그래머스 네트워크 - C++

코딩테스트 연습 - 네트워크

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

using namespace std;

bool visit[210];

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

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

int solution(int n, vector<vector<int>> computers) {
    int ans = 0;
    
    for(int i = 0; i < n; i++){
        if(!visit[i]){
            //bfs(i, computers, n);
            dfs(i, computers, n);
            ans++;
        }
    }
    return ans;
}

---

 문제를 보고 나서는 가장 익숙한 bfs로 먼저 풀었습니다. 평범하게 큐를 이용해서 탐색을 진행했으며 큐에 새 원소가 들어가는 조건은 아직 방문하지 않은 네트워크, 연결이 되어 있는 네트워크입니다. 이를 통해서 탐색을 쭉 하면 ans 변수로 네트워크의 갯수가 카운트되어 리턴됩니다.

 

 dfs의 경우는 더 간단하게 위와 같은 조건이라면 그 지점에서 dfs를 또 실행해 처리하는 것입니다.