[프로그래머스 level 3] 네트워크 (C++)

BFS 또는 DFS로 풀 수 있는 문제이다.

 

위 그래프는 2개로 나눌 수 있다.

 

 

위 그래프는 하나로 연결된 하나의 그래프이다.

 

 

모든 노드는 BFS 탐색의 시작점이 될 수 있다.

BFS를 통해 방문한 노드는 방문 기록을 남기게 되고, 시작점이 되지 못한다.

시작점이 없을 때까지 BFS를 수행하고, 문제의 답은 BFS를 수행한 횟수가 된다.

 

 

개인적으로 이 문제를 비롯한 기본 bfs, dfs문제들이 왜 level 3인지 이해가 되지 않는다.

 

최종 코드

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

using namespace std;

vector<int> adj[201];
bool visited[201];

void bfs(int start){
    queue<int> que;
    que.push(start);
    visited[start] = true;
    
    while(!que.empty()){
        int now = que.front();
        que.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i];
            if(!visited[next]){
                visited[next] = true;
                que.push(next);
            }
        }
    }
}

int solution(int n, vector<vector<int>> com) {
    int answer = 0;
    
    for(int i = 0; i < com.size(); i++){
        for(int j = 0; j < com[i].size(); j++){
            int now = com[i][j];
            if(!now) continue;
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }
    
    for(int i = 0; i < n; i++){
        if(visited[i]) continue;
        bfs(i);
        answer++;
    }
    
    return answer;
}