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

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

✏️ 아이디어

n computers 3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] → 2 3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] → 1

computers[0]은 본인, 2번과 연결 computers[1]은 1번, 본인과 연결 computers[2]은 본인과 연결

-> 본인 제외하고 연결되어있는지 확인해야할듯 노드로 만들고 next에 본인 제외 (1)로 연결된 노드 추가

각 노드를 순차 방문하면서 끝까지 들어가기 dfs(stack) 방문이 끝났다면 count+1 해서 네트워크 개수 증가하기

구현해보기 Node

number boolean visited List<Node> next

Node 1번부터 순차적으로 분석하기 현재 노드가 visited이면 넘어감 현재 노드를 stack에 push하기 stack이 !isEmpty() 인 동안

pop visited() for(node.next()) visited 아니면 push

count++ stack.clear

 

💻 코드1

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

class Solution3 {
    class Node {
        int number;
        boolean visited;
        List<Integer> links;

        public Node(int number) {
            this.number = number;
            this.visited = false;
            this.links = new ArrayList<>();
        }

        public void link(int[] links){
            for(int i = 0; i < links.length; i++) {
                    if(this.number != i && links[i] == 1){
                        this.links.add(i);
                    }
            }
        }

        public boolean isVisited(){
            return this.visited;
        }

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

        public List<Integer> getLinks(){
            return this.links;
        }

    }

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

        List<Node> nodes = new ArrayList<>();
        IntStream.range(0, n).forEach(i -> nodes.add(new Node(i)));

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

        Deque<Node> stack = new ArrayDeque<>();
        int count = 0;

        for(Node node : nodes) {
            if(node.isVisited()) continue;

            stack.push(node);

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

                now.visit();

                for(int next : now.getLinks()) {
                    if(!nodes.get(next).isVisited()){
                        stack.push(nodes.get(next));
                    }
                }
            }
            stack.clear();
            count++;
        }

        return count;

    }
}

일단 아이디어대로 짜보니 한 번에 돌아갔다. 노드마다 방문 여부를 들고 있게 하고, 스택으로 dfs를 흉내내는 방식인데 생각보다 깔끔하게 맞아들어가서 신기했다.

다시 보니 몇 가지 거슬리는 부분이 있었다.

• for문 안에서 stack.clear()를 매번 호출하는데, while문이 끝나면 이미 스택은 비어있는 상태라 사실 필요 없는 코드였다.
• dfs 로직이 solution 메서드 안에 그대로 박혀있어서 나중에 다시 보면 한눈에 흐름이 안 들어올 것 같았다.

그래서 dfs 부분을 메서드로 따로 빼서 정리해봤다.

💻 코드2 (리팩토링)

package Programmers.lv3.java.네트워크_dfs;

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

class Solution4 {
    class Node {
        private int number;
        private boolean visited;
        private List<Integer> links;

        public Node(int number) {
            this.number = number;
            this.visited = false;
            this.links = new ArrayList<>();
        }

        public void link(int[] links) {
            for(int i = 0; i < links.length; i++) {
                if(this.number != i && links[i] == 1) {
                    this.links.add(i);
                }
            }
        }

        public boolean isVisited() { return this.visited; }
        public void visit() { this.visited = true; }
        public List<Integer> getLinks() { return this.links; }

    }

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

        List<Node> nodes = new ArrayList<>();
        IntStream.range(0, n).forEach(i -> nodes.add(new Node(i))); // 각 컴퓨터를 리스트에 저장
        IntStream.range(0, n).forEach(i -> nodes.get(i).link(computers[i])); // 각 컴퓨터와 연결된 링크를 저장

        Deque<Node> stack = new ArrayDeque<>();
        int count = 0;

        for(Node node : nodes) { // 저장된 컴퓨터들을 순차적으로 순회 (모든 경로를 파악하기 위함)
            if(node.isVisited()) { // 이미 방문한 노드라면 통과
                continue;
            }
            dfs(node, nodes);
            count++; // 네트워크 한개 탐색 완료
        }

        return count;

    }

    public void dfs(Node node, List<Node> nodes) {

        Deque<Node> stack = new ArrayDeque<>();
        stack.push(node);

        while(!stack.isEmpty()) { // 방문하지 않은 해당 노드를 기준으로 모든 경로 탐색
            Node now = stack.pop();
            if(now.isVisited()) {
                continue;
            }
            now.visit();

            for(int next : now.getLinks()) {
                if(!nodes.get(next).isVisited()) {
                    stack.push(nodes.get(next));
                }
            }
        }
    }
}

dfs를 메서드로 분리하니 solution 쪽 흐름이 훨씬 잘 보인다. "순회하면서 안 가본 노드면 dfs 태우고 count 늘리기"라는 큰 그림만 남아서 만족스러웠다.

이왕 정리한 김에 스택 대신 재귀로도 짜보고 싶어졌다. dfs는 원래 재귀로 자연스럽게 표현되는 경우가 많다고 들었어서 직접 비교해보기로 했다.

💻 코드3 (재귀 버전)

package Programmers.lv3.java.네트워크_dfs;
// 재귀 구현
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

class Solution5 {
    class Node {
        private int number;
        private boolean visited;
        private List<Integer> links;

        public Node(int number) {
            this.number = number;
            this.visited = false;
            this.links = new ArrayList<>();
        }

        public void link(int[] links) {
            for(int i = 0; i < links.length; i++) {
                if(this.number != i && links[i] == 1) {
                    this.links.add(i);
                }
            }
        }

        public boolean isVisited() {
            return this.visited;
        }
        public void visit() {
            this.visited = true;
        }
        public List<Integer> getLinks() {
            return this.links;
        }

    }

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

        List<Node> nodes = new ArrayList<>();
        IntStream.range(0, n).forEach(i -> nodes.add(new Node(i))); // 각 컴퓨터를 리스트에 저장
        IntStream.range(0, n).forEach(i -> nodes.get(i).link(computers[i])); // 각 컴퓨터와 연결된 링크를 저장

        int count = 0;

        for(Node node : nodes) { // 저장된 컴퓨터들을 순차적으로 순회 (모든 경로를 파악하기 위함)
            if(node.isVisited()) { // 이미 방문한 노드라면 통과
                continue;
            }
            dfs(node, nodes);
            count++; // 네트워크 한개 탐색 완료
        }

        return count;

    }

    public void dfs(Node node, List<Node> nodes) {
        node.visit();

        for(int next : node.getLinks()) {
            if(!nodes.get(next).isVisited()) {
                dfs(nodes.get(next), nodes);
            }
        }
    }
}

스택으로 방문 순서를 직접 관리하던 코드1, 코드2랑 비교하면 재귀 버전은 "지금 노드를 방문하고, 안 가본 이웃이 있으면 그 이웃으로 또 들어간다"는 문장 그대로를 코드로 옮긴 느낌이라 훨씬 읽기 편했다. 다만 n이 커지면 재귀 깊이가 깊어질 수 있어서, 문제의 n 제한(200 이하)처럼 작은 범위에서는 재귀가 편하지만 그렇지 않은 경우엔 스택 방식이 더 안전할 수도 있겠다는 생각이 들었다.

✨ 더 개선할 수 있는 방법: visited 배열로 단순화

지금까지는 Node 클래스를 만들어서 number, visited, links를 각각 들고 있게 했는데, 사실 computers 배열 자체가 이미 연결 정보를 다 가지고 있어서 Node 객체 없이 visited 배열 하나만으로도 충분히 풀 수 있다. 링크 리스트를 따로 만드는 과정도 필요 없어져서 코드가 훨씬 짧아진다.

class Solution6 {

    boolean[] visited;

    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        int count = 0;

        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                dfs(i, n, computers);
                count++;
            }
        }

        return count;
    }

    private void dfs(int current, int n, int[][] computers) {
        visited[current] = true;

        for(int next = 0; next < n; next++) {
            if(computers[current][next] == 1 && !visited[next]) {
                dfs(next, n, computers);
            }
        }
    }
}

Node 클래스도, links 리스트도 다 사라지고 visited 배열 하나와 computers 배열만으로 탐색이 끝난다. computers[current][next]를 그때그때 확인하는 거라 링크를 미리 뽑아두는 과정(link 메서드)도 필요 없다. 코드1~3에서 Node를 만들고 링크를 세팅하던 부분이 사실은 없어도 되는 준비 과정이었다는 걸 이 버전을 짜보고서야 알았다.

📖 새로 배운 부분

1. dfs를 스택으로 구현할 때 방문 체크는 push할 때 하는 게 아니라 pop해서 실제로 처리할 때 하는 게 맞다는 걸 다시 확인했다. push 시점에 체크하면 같은 노드가 중복으로 스택에 들어가는 걸 못 막는다.
2. solution 메서드 안에 로직을 다 넣는 것보다 dfs를 별도 메서드로 분리하니 코드 리뷰하듯 스스로 다시 봤을 때 훨씬 이해가 빨랐다.
3. 같은 dfs라도 스택 기반과 재귀 기반은 코드의 "읽는 느낌"이 다르다. 재귀는 문제를 말로 설명하는 흐름과 거의 똑같이 짜여서 로직 검증이 쉬웠다.
4. 항상 Node 클래스로 그래프를 감싸야 하는 건 아니었다. computers처럼 연결 정보가 이미 2차원 배열로 주어져 있으면, visited 배열만으로도 충분히 dfs를 돌릴 수 있다는 걸 이번에 깨달았다.

참고

• 네트워크 - 프로그래머스

프로그래머스