일단 시작해보는 블로그

[알고리즘_풀이] 프로그래머스 - 네트워크 java 본문

CS/알고리즘 풀이

[알고리즘_풀이] 프로그래머스 - 네트워크 java

Selina Park 2020. 3. 11. 13:32
import java.util.*;
class Solution {
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        Node[] graph = new Node[n+1];
        for(int i=1; i<=n; i++) {
            graph[i] = new Node(i);
        }
        
        // 인접리스트 추가
        for(int i=0; i<computers.length; i++) {
            for(int j=0; j<computers[0].length; j++) {
                if(i == j || computers[i][j] == 0) continue;
                if(!graph[i+1].adjacent.contains(j+1)) {
                    graph[i+1].adjacent.add(j+1);
                }
            }
        }
        
        answer = dfs(graph, 1, n);
        
        return answer;
    }
    
    public int dfs(Node[] graph, int begin, int n) {
        int rtn = 0;
        Stack<Integer> stack = new Stack<>();
      
        for(int i=1; i<=n; i++) {
            if(graph[i].checked == true) continue;
            
            rtn++;
            
            stack.add(i);
            graph[i].checked = true;
            
            while(!stack.isEmpty()) {
                int out = stack.pop();
                graph[out].checked = true;
                for(int adj: graph[out].adjacent) {
                    if(graph[adj].checked == false) {
                        stack.add(adj);
                    }
                }
            }
        }
        
        return rtn;
    }
    
    class Node {
        int key;
        LinkedList<Integer> adjacent;
        boolean checked;
        Node(int key) {
            this.key = key;
            this.adjacent = new LinkedList<>();
            this.checked = false;
        }
    }
}
Comments