[프로그래머스] 네트워크 BFS, DFS - JAVA

DFS, BFS 로 풀어봤다!

 

DFS

import java.util.*;
class Solution {
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> graph;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        graph = new ArrayList<>();
        for(int i = 0; i < n; i++){graph.add(new ArrayList<>());}
        for(int i=0;i<computers.length;i++){
            for(int j=0;j<computers[i].length;j++){
                if(i == j) continue;
                if(computers[i][j] == 1){
                    graph.get(i).add(j);
                }
            }
        }
        visited = new boolean[n];
        for(int i=0;i<n;i++){
            if(!visited[i]){
                dfs(i, graph);
                answer++;
            }
        }

        return answer;
    }
    static void dfs(int v, ArrayList<ArrayList<Integer>> graph){
        visited[v] = true;
        for(int next: graph.get(v)){
            if(!visited[next]){
                dfs(next, graph);
            }
        }
    }
}

 

 

BFS

import java.util.*;
class Solution {
    static boolean visited[];
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        ArrayList<ArrayList<Integer>> edge = new ArrayList<>();
        for(int i=0;i<n;i++) edge.add(new ArrayList<>());
        for(int i=0;i<computers.length;i++){
            for(int j=0;j<computers[i].length;j++){
                if(i == j) continue;
                if(computers[i][j] == 1) edge.get(i).add(j);
            }
        }
        
        visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        
        for(int i=0;i<n;i++){
            if(visited[i]) continue;
            q.offer(i);
            answer++;
            while(!q.isEmpty()){
                int cur = q.poll();
                if(visited[cur]) continue;
                visited[cur] = true;

                for(int next: edge.get(cur)){
                    if(!visited[next]){
                        q.offer(next);                    
                    }
                }

            }
        }
      
        
        return answer;
    }
}