[프로그래머스] 네트워크 - JAVA

문제 링크

문제 정의

• 컴퓨터의 개수 $n$개
• 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때
• 네트워크의 개수 구하는 문제

---

접근 방법

이 문제는 computers 배열 활용해
Flood Fill과 DFS 또는 BFS를 사용해서 푸는 문제입니다.

인접 리스트 변환

이번 문제에서는 사실 변환이 필요없을 정도로 간단하지만
인접 리스트 변환을 학습하고자 추가했습니다.

그래프 문제를 해결할 때 일반적으로 ArrayList[] 타입을 사용하지만
이번 풀이에서는 성능 최적화를 위해
직접 구현한 커스텀 연결 리스트(Node[])를 활용했습니다.

자바의 Collections 프레임워크는 범용적이지만
동적 배열의 리사이징 과정이나 래퍼 객체(Integer)로 인한
메모리 오버헤드가 발생할 수 있습니다.

반면, 필요한 데이터만 담은 Node 객체를 정의해 인접 리스트를 관리하면
메모리 사용량을 최소화하고 순회 속도를 높일 수 있어
엄격한 시간/메모리 제한이 있는 환경에서 더욱 효율적인 최적화가 가능합니다.

---

Flood Fill

DFS BFS 문제에서 종종 나오는 유형입니다.
대부분 $N*M$ 영역에서 인접한 지역들을 구분할 때 사용되는 알고리즘입니다.

이번 문제에서는 서로 연결된 컴퓨터들을 하나의 네트워크로 인식하도록
DFS를 수행해 방문 처리를 하고
network값을 1 증가시켜 하나의 네트워크라는 처리를 해줍니다.

---

DFS

이번 문제에서는 DFS BFS 둘 다 풀 수 있는 문제입니다.
별도의 조건 없이 내부에서 방문 처리만 하는 간단한 로직일 경우에는
큐를 사용하는 BFS보다 DFS가 성능적으로 더 뛰어나서 DFS를 사용했습니다.

---

코드

import java.util.*;

class Node {
    int v;
    Node node;
    
    public Node (int v, Node node) {
        this.v = v;
        this.node = node;
    }
}


class Solution {
    static Node[] graph;
    public int solution(int n, int[][] computers) {
        init (n, computers);
        return floodFill(n, computers);
    }
    
    static void dfs (int v, boolean[] visited) {
        for (Node node = graph[v]; node != null; node = node.node) {
            int nv = node.v;
            if (!visited[nv]) {
                visited[nv] = true;
                dfs(nv, visited);
            }
        }
    }
    
    static int floodFill(int n, int[][] computers) {
        int network = 0;
        boolean[] visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, visited);
                network++;
            }
        }
        
        return network;
    }
    
    static void init(int n, int[][] computers) {
        graph = new Node[n];
        
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (computers[i][j] == 1) {
                    graph[i] = new Node(j, graph[i]);
                    graph[j] = new Node(i, graph[j]);
                }
            }
        }
    }
}