네트워크

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

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

연결여부를 확인하는 문제. 큐에 담아두고 문제를 푼다.

import java.util.*;
 
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        
        
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            
            answer += 1;
            
            Queue<Integer> queue = new LinkedList();
            queue.offer(i);
            
            while(!queue.isEmpty()) {
                int computer = queue.poll();
                int[] connections = computers[computer];
                
                for (int j = 0; j < connections.length; j++) {
                    if (computer == j) continue; // 자기 자신이면 패스
                    if (visited[j]) continue;
                    if (connections[j] == 1) {
                        visited[j] = true;
                        queue.offer(j);
                    }
                }
            }
        }
        
        return answer;
    }
}

 

stack의 풀이

import java.util.*;
 
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        
        
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            
            answer += 1;
            
            Stack<Integer> stack = new Stack();
            stack.push(i);
            
            while(!stack.isEmpty()) {
                int computer = stack.pop();
                int[] connections = computers[computer];
                
                for (int j = 0; j < connections.length; j++) {
                    if (computer == j) continue; // 자기 자신이면 패스
                    if (visited[j]) continue;
                    if (connections[j] == 1) {
                        visited[j] = true;
                        stack.push(j);
                    }
                }
            }
        }
        
        return answer;
    }
}