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

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

문제 요약

 컴퓨터의 개수 n과 각 컴퓨터들의 연결 여부를 저장한 computers 2차원 배열을 받아서, 네트워크 (연결된 컴퓨터 그룹)의 개수를 반환하는 문제이다.

 

문제 풀이

 어제에 이은 두 번째 탐색문제이다. 문제의 난이도는 전혀 어렵지 않았고, dfs로 풀어야겠다고 생각은 바로 했는데 푸는 과정에서 List 배열을 만들어서 연결된 컴퓨터의 값들을 저장한다던지, 이미 연결되었다고 밝혀진 컴퓨터를 탐색한다던지, Set에 값들을 모은다던지 하는 굳이 필요없는 코드들이 생겨났다. 정답 처리는 받았지만 코드가 너무 비 효율적이라는 느낌을 받아서 다시 리팩토링 하였다.

 

 일단 boolean 배열 visit을 선언해서 한 번 탐색되었거나, 다른 컴퓨터와 연결되었다고 밝혀진 컴퓨터에는 다시 불필요하게 접근하지 않았다. 방문하지 않았던 컴퓨터들을 하나씩 DFS로 탐색해서 연결된 컴퓨터들을 전부 방문 처리한 후 네트워크의 개수를 1개씩 증가시켰다.

 

나의 코드

class 네트워크 {
    boolean[] visit;    //  방문 여부 배열

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

        for (int i = 0; i < n; ++i) {
            if (!visit[i]) {    //  아직 연결된 네트워크가 없을 때만
                dfs(computers, i);
                answer++;
            }
        }
        return answer;
    }

    public void dfs(int[][] computers, int idx) {
        visit[idx] = true;
        for (int i = 0; i < computers[idx].length; ++i) {
            if (computers[idx][i] == 1 && !visit[i])    //  idx 번 컴퓨터와 연결되어 있으면서 방문한 적 없는 컴퓨터만
                dfs(computers, i);
        }
    }
}