Coding Test] 네트워크 문제(BFS)

[Programmers School 문제 링크]

• Code

#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    queue<int> q;
    set<int> s;
    
    for(int i = 0; i < n; i++)
    {
        if(s.find(i) != s.end()) continue;
        q.push(i);
        s.insert(i);
        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            for(int target = 0; target < n; target++)
            {
                if(cur == target || s.find(target) != s.end())    
                    continue;
                if(computers[cur][target] == 1)
                {
                    q.push(target);
                    s.insert(target);
                }
            }
        }
        answer++;
    }
    
    return answer;
}

---

• 변수 별 역할

queue<int> q;    //BFS 순회용
set<int> s;      //방문 체크용(카운팅된 네트워크에 속하는 노드들

• BFS 이전에 for문 부분

//모든 노드에서 시작한 경우를 봐야하므로 N번 BFS를 동작해야한다.
for(int i = 0; i < n; i++)
{
    //이미 연결되어있는 네트워크는 제외
    if(s.find(i) != s.end()) continue;
    
    q.push(i);    //시작 노드
    s.insert(i);  //연결된 노드
    
    //BFS
    //...
    
    //하나의 네트워크 완성
    answer++;
}

• BFS 탐색 부분

//BFS
while(!q.empty())
{
    //이번 노드
    int cur = q.front();
    q.pop();
    
    //이번 노드가 다른 노드들과 연결되어있는지 확인하기 위한 Loop
    for(int target = 0; target < n; target++)
    {
        //이번 노드와 목표 노드가 같음 or 등록된 네트워크에 속하는 노드
        if(cur == target || s.find(target) != s.end()) continue;
        
        //연결된 적 없는 노드로 가는 길이 있다면
        if(computers[cur][target] == 1)
        {
            q.push(target);    //목표 노드부터 확인하기 위해 큐에 추가
            s.insert(target);  //연결된 노드 기록
        }
    }
}