[Programmers] 깊이/너비 우선 탐색(DFS/BFS) > 네트워크(c++)

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

DFS방법으로 해결했다.

computer[i][j]에서 i==j 일때는 자기자신이므로 dfs벡터에 넣지 않고,

연결되어있는 인덱스 (1과 2가 이어져있으면 dfs[1].push_back(2), dfs[2].push_back(1) ) 이런식으로 dfs에 모두 넣은 후,

노드는 0번째부터 n-1까지 시작하여 방문하지 않은 노드에 한해서만 DFS를 실행하고, DFS가 한번 실행될때마다 net++를 해줬다.

DFS로 노드들이 한번에 연결된다면 DFS한번 실행할때 모든 노드가 isVisited = true가 되므로 net은 1이될것이고, 

연결되지 않은 노드가 있다면 isVisited가 false이므로 net을 더해줘야한다.

#include <vector>
using namespace std;
#define SIZE 201

int isVisited[SIZE] = {0,};
vector<int> dfs[SIZE];
int net = 0;

void DFS(int V){
    if(isVisited[V] == true || dfs[V].size() == 0 )  return;
    isVisited[V] = true;
    
    for(int i=0;i<dfs[V].size();i++){
        DFS(dfs[V][i]);
    }
}

int solution(int n, vector<vector<int>> computers) {
    
    for(int i=0;i<computers.size();i++){
        for(int j=0;j<computers.size();j++){
            if( i!=j && computers[i][j] == 1){
                dfs[i].push_back(j);
            }
        }
    }
    for(int i=0;i<n;i++) {
        if(isVisited[i] == false) {
            DFS(i);
            net++;
        }
    }
    return net;
}

 

 

 

---

 

main포함 코드

#include <vector>
#include <iostream>
using namespace std;
#define SIZE 201

int isVisited[SIZE] = {0,};
vector<int> dfs[SIZE];
int net = 0;

void DFS(int V){
    if(isVisited[V] == true || dfs[V].size() == 0 )  return;
    isVisited[V] = true;
    
    for(int i=0;i<dfs[V].size();i++){
        DFS(dfs[V][i]);
    }
}

int solution(int n, vector<vector<int>> computers) {
    
    for(int i=0;i<computers.size();i++){
        for(int j=0;j<computers.size();j++){
            if( i!=j && computers[i][j] == 1){
                dfs[i].push_back(j);
            }
        }
    }
    for(int i=0;i<n;i++) {
        if(isVisited[i] == false) {
            DFS(i);
            net++;
        }
    }

    return net;
}

int main(int argc, const char *argv[])
{
    int n= 3;
    vector<vector<int>> computers;
    
    vector<int> a,b,c;
    
    a.push_back(1);
    a.push_back(1);
    a.push_back(0);
    
    b.push_back(1);
    b.push_back(1);
    b.push_back(1);
    
    c.push_back(0);
    c.push_back(1);
    c.push_back(1);
    
    computers.push_back(a);
    computers.push_back(b);
    computers.push_back(c);
    
    cout << solution(n, computers);
    
    return 0;
}

 

---

시도한 테스트케이스

3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]]  - Return 2

3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] - Return 1

4 [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]] - Return 1

2 [[1, 0], [0, 1]] - Return 2

3 [[1, 0, 0], [0, 1, 0], [0, 0, 1]] - Return 3

1 [[1]] - Return 1