[프로그래머스/BFS] Level 3 네트워크 (JAVA)

문제

---

풀이 (2021.01.04)

보자마자 중첩 ArrayList 그래프와 Queue를 사용한 bfs로 풀어야겠다는 생각이 들었다. 그러고 나서 computers 배열만으로도 풀 수 있지 않을까 하는 생각이 들었지만, 일단 내가 여태 공부했던 걸 백지 상태에서도 잘 구현할 수 있는지 확인하기 위해 내가 아는 대로 해보았다.

주요 로직은 다음과 같다.

• n개의 노드에 대해 bfs를 실행하고, 그 노드를 포함한 새로운 네트워크가 생길 경우 count를 증가시킨다.
• bfs에서는 근접 노드들에 대해 모두 visited를 갱신함으로써 네트워크에 포함되었음을 표시한다.

코드

import java.util.*;

class Solution {

    private static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;
    private static int count;

    public int solution(int n, int[][] computers) {

        initGraph(n, computers);
        initVisited(n);
        countNetworks(n);
        return count;
    }


    private void initGraph(int n, int[][] computers) {
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
            for (int j = 0; j < computers[i].length; j++)
                if (computers[i][j] == 1 && i != j)
                    graph.get(i).add(j);
        }
    }

    private void initVisited(int n) {
        visited = new boolean[n];
        Arrays.fill(visited, false);
    }

    private void countNetworks(int n) {
        for (int i = 0; i < n; i++)
            bfs(i);
    }

    private void bfs(int node) {
        if (visited[node])
            return;

        Queue<Integer> queue = new LinkedList<>();
        visited[node] = true;
        queue.offer(node);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int adjacent : graph.get(current))
                if (!visited[adjacent]) {
                    queue.offer(adjacent);
                    visited[adjacent] = true;
                }
        }
        count++;
    }
}

---

풀이 (2021.05.29)

그래프 없이 당연히 computers 배열만 가지고도 풀 수 있는 문젠데, 1월에 풀 때는 참 귀엽게도 푼 것 같다 ^^;;

코드

import java.util.*;

class Solution {
    
    private static final int CONNECTED = 1;
    
    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;
            
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            while (!queue.isEmpty()) {
                int current = queue.poll();
                visited[current] = true;
                
                for (int j=0 ; j<n ; j++)
                    if (current != j && computers[current][j] == CONNECTED && !visited[j])
                        queue.offer(j);
            }
            answer++;
        }
        return answer;
    }
}