[프로그래머스] 네트워크

문제  : Level3 네트워크

[ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/43162

 

[ 문제풀이 ]

 

이 문제는 컴퓨터의 연결 정보가 주어 질 때 

이 연결 정보를 통해서 몇 개의 네트워크가 존재하는지를 구하는 문제이다

BFS 탐색을 통해서 연결되어 있는 모든 컴퓨터 즉, 모든 노드 탐색하면서 

방문한 노드를 check 배열에 표시해 주었다

정답은 BFS의 호출 횟수이다 

 

여기서 주의할 점은

컴퓨터의 연결 정보가 인접 리스트가 아닌 인접 행렬로 주어진다는 점이다

그 점만 주의해서 BFS 탐색 코드만 잘 짜주면 된다.

 

 

[소스 코드]

#include <string>
#include <vector>
#include <queue>
using namespace std;
const int MAX = 200;
bool check[MAX];
void bfs(int start, int n, vector<vector<int>>& computers) {
    queue<int> q;
    check[start] = true;
    for (int i = 0; i < n; i++) {
        int connected = computers[start][i];
        if (connected == 1 && !check[i]) {
            check[i] = true;
            q.push(i);
        }
    }
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = 0; i < n; i++) {
            int connected = computers[x][i];
            if (!connected || check[i]) continue;
            check[i] = true;
            q.push(i);
        }
    }
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for (int i = 0; i < n; i++) {
        if (!check[i]) { bfs(i, n, computers), answer += 1; };
    }
    return answer;
}