네트워크

본 풀이는 java 언어를 사용하였습니다.
문제 보러가기

풀이

문제가 잘 이해가 안되었었는데, 컴퓨터가 하나의 선으로 연결되어 있어야지만 1개의 네트워크로 인정된다.
즉, 아래의 경우는 2개의 네트워크가 된다.

컴퓨터 한 대가 어디까지 연결되어 있는지 끝까지 탐색해야 하므로, 깊이 우선 탐색인 DFS 를 사용했다.
DFS 는 재귀나 Stack 을 이용해서 풀 수 있는데 나는 재귀를 이용했다.

코드

public class Solution {

    public static final int CONNECT = 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;
            }

            dfs(computers, i, visited);
            answer++;
        }

        return answer;
    }

    private void dfs(int[][] computers, int i, boolean[] visited) {
        visited[i] = true;

        for (int j = 0; j < computers.length; j++) {
            if (isValid(computers, i, visited, j)) {
                dfs(computers, j, visited);
            }
        }
    }

    private boolean isValid(int[][] computers, int i, boolean[] visited, int j) {
        return i != j && computers[i][j] == CONNECT && !visited[j];
    }
}

회고

문제 자체는 어렵지 않았는데 DFS 문제를 오랜만에 풀었더니 문제 파악하기가 어려웠다..
탐색 문제를 익숙해 질 때까지 주기적으로 풀어야 겠다.