[BFS, 난이도 중하] 프로그래머즈, 네트워크

BFS를 돌며 연결된 간선은 모두 방문 처리를 해주고, 더 이상 방문할 노드가 없을 경우 중단 한다.

모든 컴퓨터를 탐색하면서, 아직 방문하지 않은 컴퓨터일 경우 BFS를 시작해주고, BFS를 새로 시작할 때마다 answer를 1씩 증가시키면 문제가 해결된다. 

 

한번 BFS를 수행하면, BFS의 시작점 컴퓨터와 같은 네트워크안에 있는 모든 컴퓨터가 방문처리 되는 것이다.

즉, answer = BFS 수행 횟수 가 되는 것이다.

 

테스트 케이스 13개 모두 통과

 

#include <vector>
#include <queue>
using namespace std;
bool visited[201];
vector<int> a[201];
queue<int> q;

void bfs() {
    while(!q.empty()){
        int x = q.front();
        for(int i=0;i<a[x].size();i++){
            int y = a[x][i];
            if(!visited[y]) {
                visited[y]=true;
                q.push(y);
            }
        }
        q.pop();
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j && computers[i][j]) a[i].push_back(j); 
        }
    }
    for(int i=0;i<n;i++){
        if(!visited[i]) {
            visited[i]=true;
            q.push(i);
            bfs();
            answer++;
        }
    }
    return answer;
}