Table of contents

프로그래머스 네트워크

노드의 개수와 연결정보가 주어졌을 때, 만들어진 네트워크의 수를 구하는 문제이다. 처음 문제를 이해하는데 시간이 조금 걸리긴 했지만 단순 그래프 탐색 문제였다.

boolean[] visited;

public int solution(int n, int[][] computers) {
    visited = new boolean[n];
    int answer = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            answer++;
            dfs(i, computers, n);
        }
    }
    return answer;
}

private void dfs(int start, int[][] computers, int n) {
    visited[start] = true;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && computers[start][i] == 1) {
            dfs(i, computers, n);
        }
    }
}

각 노드를 root로 취급하여 dfs를 수행한다. 해당 노드가 아직 방문되지 않은 경우를 하나의 네트워크로 취급한다. 이전 탐색까지 해당 노드가 방문되지 않았다는 것은, 해당 노드에 연결된 네트워크를 아직 탐색하지 않았음을 의미한다.

그래프, 노드, 스택을 이용한 dfs탐색 코드는 다음과 같다.

class Solution {
    public int solution(int n, int[][] computers) {
        Network network = new Network(n, computers);
        return network.networkCount();
    }

    class Network {
        Computer[] computers;

        public Network(int n, int[][] computers) {
            this.computers = new Computer[n];
            for (int i = 0; i < n; i++) {
                this.computers[i] = new Computer(i);
            }

            for (int i = 0; i < n; i++) {
                int[] edges = computers[i];
                for (int j = 0; j < edges.length; j++) {
                    if (i == j || computers[i][j] == 0) continue;
                    addEdge(i, j);
                }
            }
        }

        public int networkCount() {
            int result = 0;

            for (int i = 0; i < computers.length; i++) {
                Computer computer = computers[i];
                if (!computer.marked) {
                    result++;
                    dfs(computer);
                }
            }
            return result;
        }

        private void dfs(Computer root) {
            Stack<Computer> stack = new Stack<>();
            root.marked = true;
            stack.push(root);
            while (!stack.isEmpty()) {
                Computer computer = stack.pop();
                for (Computer adjacent : computer.adjacents) {
                    if (!adjacent.marked) {
                        adjacent.marked = true;
                        stack.push(adjacent);
                    }
                }
            }
        }

        class Computer {
            int data;
            boolean marked;
            List<Computer> adjacents;

            public Computer(int data) {
                adjacents = new LinkedList<>();
                this.data = data;
            }
        }

        public void addEdge(int a, int b) {
            Computer c1 = computers[a];
            Computer c2 = computers[b];

            if (!c1.adjacents.contains(c2)) {
                c1.adjacents.add(c2);
            }
            if (!c2.adjacents.contains(c1)) {
                c2.adjacents.add(c1);
            }
        }
    }
}