[프로그래머스] 네트워크 (Java)

문제

• 문제 및 제한 사항, 입출력 예시는 프로그래머스 참고

알고리즘 아이디어

사실 아이디어라고 할것도 없다 문제 입력부터 근접 매트릭스로 주는 명백한 그래프 탐색 문제이다. DFS와 BFS 모두 사용하여 풀 수 있는 기초적인 문제이다. 연결된 컴퓨터들은 그 중하나의 노드에서부터 탐색하면 방문가능하기 때문에 순차적으로 새로운 DFS/BFS 탐색이 시작하는 횟수만 세면 네트워크 수를 알 수 있다.

풀이

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;
            }
            this.iterativeDfs(computers, i, visited);
            answer++;
        }
        
        return answer;
    }
    
    private void recursiveDfs(int[][] computers, int source, boolean[] visited) {
        visited[source] = true;
        for (int i = 0; i < computers[source].length; i++) {
            if (computers[source][i] == 1 && !visited[i]) {
                recursiveDfs(computers, i, visited);
            }
        }
    }
    
    private void iterativeDfs(int[][] computers, int source, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();
        stack.push(source);
        
        while(!stack.isEmpty()) {
            int com = stack.pop();
            visited[com] = true;
            
            for (int i = computers[com].length-1; i >= 0; i--) {
                if (computers[com][i] == 1 && !visited[i]) {
                    stack.push(i);
                }
            }
            
        }
    }
    
    private void bfs(int[][] computers, int source, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>();
        q.add(source);
        visited[source] = true;
        
        while (!q.isEmpty()) {
            int com = q.poll();
            for (int i = 0; i < computers[com].length; i++) {
                if (computers[com][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
    
}

결과

• recursiveDfs
• iterativeDfs
• bfs