네트워크

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

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

#include <string>
#include <vector>
#include <iostream>

using namespace std;

void dfs(vector<vector<int>>&nodelist,vector<int>&check, int node){
    check[node]=1;

    for(int j=0; j<nodelist[node].size(); j++){
     
    if( check[nodelist[node][j]]==0){
    dfs(nodelist,check,nodelist[node][j]);
    }
       }
    
    return;
}

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

- 인접리스트를 통해서 풀었습니다.

 

<java 코드>

import java.util.*;
class Solution {
    
    
    public void dfs(int k, ArrayList<ArrayList<Integer>> arr, int[] chk){
            for(int i=0; i<arr.get(k).size(); i++){
                int tmp = arr.get(k).get(i);
                if(chk[tmp]==0){
                    chk[tmp]=1;
                    dfs(tmp,arr,chk);
                }
            }
    }
    
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
        int[] chk = new int[n];
        for(int i=0; i<n; i++){
            arr.add(new ArrayList<>());
        }
        
        for(int i=0; i<computers.length; i++){
            for(int j=0; j<computers[i].length; j++){
                if(i!=j && computers[i][j]==1){
                    arr.get(i).add(j);
                    arr.get(j).add(i);
                }
            }    
        }
        
        for(int i=0; i<n; i++){
            if(chk[i]==0){
                answer ++;
                dfs(i,arr,chk);
                
            }
        }

        return answer;
    }
}