프로그래머스 : 네트워크

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers

네트워크의 개수를 return 

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

ncomputersreturn

3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

A110

B110

C001 ->2(A-B, C)

 

110

111

011 -> 1(A-B-C)

---

풀이 : 

bool v[200]; 로 방문 했는지 안했는지 체크 

dfs 를 사용해서 풀겠다.

---

#include <string>
#include <vector>

using namespace std;

bool v[200];
vector<vector<int> > map;
int num;

void dfs(int index){
    v[index] = true;
    for(int i=0; i<num; i++){
        if(map[index][i] == 1&& v[i]==false){
            dfs(i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    num = n;
    map = computers;
    for(int i=0; i<n; i++){
        if(v[i] == false){
            dfs(i);
            answer++;
        }
    }
    return answer;
}

---

bfs 로도 풀어 봤다.

---

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

using namespace std;

bool v[200];
vector<vector<int>> map;
int num;

void bfs(int index){
    queue<int> q;
    q.push(index);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        if(v[now]==false){
            v[now] = true;
            for(int i=0; i<num; i++){
                if(v[i]==false&&map[now][i]){
                    q.push(i);
                }
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    num= n;
    map = computers;
    
    for(int i=0; i<n; i++){
        if(v[i]==false){
            bfs(i);
            answer++;
        }
    }
    
    return answer;
}