네트워크

문제정의

---

네트워크의 개수가 몇 개인지 판별하는 문제이다. 기본적인 탐색문제이다.

문제 링크

문제풀이

---

전체 코드는 다음과 같다.

import java.util.*;

public class Network {

    //프로그래머스 문제풀이 level3 네트워크
    public static void main(String[] args) {
        int[][] computers = {
            {1, 1, 0},
            {1, 1, 0},
            {0, 0, 1}
        };
        int n = 3;
        int answer = 0;
        boolean[] visited = new boolean[n];
        for(int i = 0 ; i < n; i++)
        {
            if(!visited[i])
            {
                answer++;
                visited[i] = true;
                Stack<Integer> stack = new Stack<>();
                stack.push(i);
                while(!stack.empty())
                {
                    int t = stack.peek();
                    stack.pop();
                    for(int j = 0; j < n; j++)
                    {
                        if(computers[t][j] == 1 && !visited[j])
                        {
                            visited[j] = true;
                            stack.push(j);
                        } 
                            
                    }
                }
            }
        }
    }
    
}

전형적인 탐색문제라 어렵지 않다. 일단 각 컴퓨터를 한번이라도 체크했는지 확인하는 불리안 배열을 생성한다. 그리고 이 배열을 순회하며 만약 한 번도 체크하지 않은 컴퓨터라면 dfs를 실시 한다. 필자는 스택을 이용해서 dfs를 구현했다.

반복 횟수를 계산해보자면 $(m+n-2)(m+n-2)m\ast m$이 된다. 따라서 최고차항을 따로 떼어내면 최종 시간복잡도는 $O(m^2{n}^2)$이다.

테스트

예전만 해도 dfs가 왜 스택이고 bfs는 왜 큐인지 이해가 잘 안갔는데 어느 새, 혼자서 아무것도 참고하지 않고 dfs를 구현할 수 있게 되었다. 늦은 감이 없지 않아 있지만, 그래도 성장했음을 느낀다.