[BFS/DFS]네트워크

 

접근

네트워크 = 그래프

모든 서브 그래프의 수를 구하는 문제.

 

해결방법

1) 모든 노드를 방문 할 때까지 BFS를 몇번 수행해야하는지 확인.

 

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

void BFS(vector<vector<int>> computers,int node, vector<bool>& is_visited)
{
    queue<int> q;
    q.push(node);

    while(!q.empty())
    {
        auto cur_node = q.front();
        q.pop();

        is_visited[cur_node]=true;

        //cur_node와 연결되어있고 방문 안했으면 방문. computers[cur_node]
        for(int i=0;i<computers.size();i++)
        {
            if(computers[cur_node][i]==1&&cur_node!=i&&is_visited[i]==false)
                q.push(i);
        }
    }

}


int solution(int num, vector<vector<int>> computers)
{
    vector<bool> is_visited(num,false);
    int res=0;
    for(int i=0;i<num;i++)
    {
        if(is_visited[i]==true)
            continue;

        BFS(computers,i,is_visited);

        res++;
    }
    return res;
}

 

 

초기 오답 내용

for(auto computer : computers[cur_node])
{
    if(computer==1&&computer!=cur_node&&is_visited[computer]==false)
        q.push(computer);
}

 

- 구현시, 배열의 값과 배열 순번을 혼재하여 사용해 문제 발생