[프로그래머스] 네트워크 Lv3 JAVA [탐색][엄탱]

문제 링크

프로그래머스

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어 있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

해설

해당 문제는 DFS 알고리즘으로 풀 수 있는 문제이다.

접근 방법은 이렇게 하였다.

 

1. 우선 탐색한 컴퓨터인지 표시하기 위한 배열을 하나 만든다.

2. computers 배열을 완전 탐색하면서 방문하지 않은 컴퓨터 A를 Stack에 넣어주고 네트워크 개수를 하나 증가시킨다.

3. 컴퓨터 A와 연결된 컴퓨터들을 찾기 위해 DFS 알고리즘을 사용하면서 연결되어 있는 컴퓨터들을 찾아가며 탐색 배열에 탐색한 컴퓨터로 체크해 준다.

 

위에서 Stack을 사용한 이유는 DFS를 하기 위해 사용하였다.

근데 생각해 보니 해당 문제는 BFS로 풀어도 무방할 것 같다는 생각을 했다.

어차피 간접적으로 연결된 컴퓨터들을 찾아서 동일한 네트워크인지만 확인하는 것이니 DFS든 BFS든 상관없는 것 같다.

그래서 BFS로도 풀어봤다.

코드

1. DFS

import java.util.Stack;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;

        boolean[] visited = new boolean[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < computers.length; i++) {
            if (visited[i]) {
                continue;
            }

            stack.push(i);
            answer++;

            while(!stack.isEmpty()) {
                int cur = stack.pop();

                if (visited[cur]) {
                    continue;
                }

                visited[cur] = true;

                int[] computer = computers[cur];

                for (int j = 0; j < computer.length; j++) {
                    if (visited[j] || computer[j] == 0){
                        continue;
                    }

                    stack.push(j);
                }
            }
        }


        return answer;
    }
}

2. BFS

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;

        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < computers.length; i++) {
            if (visited[i]) {
                continue;
            }

            queue.offer(i);
            answer++;

            while(!queue.isEmpty()) {
                int cur = queue.poll();

                if (visited[cur]) {
                    continue;
                }

                visited[cur] = true;

                int[] computer = computers[cur];

                for (int j = 0; j < computer.length; j++) {
                    if (visited[j] || computer[j] == 0){
                        continue;
                    }

                    queue.offer(j);
                }
            }
        }


        return answer;
    }
}