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

사진을 클릭하면 해당 문제로 이동

💡풀이 1

- node 클래스를 만들어서 풀이

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    class Node {
        String name;
        List<Node> links = new ArrayList<>();
        boolean visited = false;

        Node(String name) {
            this.name = name;
        }

        private List<Node> getLinks() {
            return this.links;
        }

        private void link(Node node) {
            this.links.add(node);
        }

        private boolean isVisited() {
            return visited;
        }

        private void visit() {
            this.visited = true;
        }
    }

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

        List<Node> nodes = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            nodes.add(new Node(String.valueOf(i)));
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i != j && computers[i][j] == 1) {
                    nodes.get(i)
                            .link(nodes.get(j));
                }
            }
        }

        int answer = 0;
        for(Node node : nodes) {
            if(node.isVisited()) {
                continue;
            }

            answer++;
            dfs(node);
        }

        return answer;

    }


    public void dfs(Node startNode) {
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(startNode);

        while(!stack.isEmpty()) {
            Node node = stack.pop();
            if(node.isVisited()) {
                continue;
            }

            node.visit();

            for(Node link : node.getLinks()) {
                if(!link.isVisited()) {
                    stack.push(link);
                }
            }

        }
    }
}

💡풀이 2

- node 클래스 없이 visited 배열을 사용하여 풀이

import java.util.ArrayDeque;
import java.util.Queue;

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

        boolean[] visited = new boolean[n];
        int answer = 0;

        for(int i = 0; i < n; i++) {
            if(visited[i]) {
                continue;
            }
            answer++;
            bfs(computers, visited, i);
        }
        return answer;
    }

    void bfs(final int[][] computers, boolean[] visited, int node) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(node);

        while(!queue.isEmpty()) {
            int now = queue.poll();
            visited[now] = true;

            for(int i = 0; i < computers[now].length; i++) {
                if(visited[i]) {
                    continue;
                }
                if(now != i && computers[now][i] == 1) {
                    queue.offer(i);
                }
            }
        }
    }
}

---