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

10 Feb 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 첫 번째 풀이
  • 두 번째 풀이

☑️ 문제

프로그래머스 43162

• 네트워크 개수를 구하는 문제
• n 개의 컴퓨터가 주어지고, computers 2차원 배열로 연결 상태가 주어진다.
• 연결된 컴퓨터 그룹(네트워크)의 개수를 반환해야 한다.

☑️ 풀이

첫 번째 풀이

//시간: 0.30ms
//메모리: 75MB

class Solution {
    static boolean[] visited;

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

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

    public void dfs(int[][] computers, int n, int start) {
        visited[start] = true;
        for (int i = 0; i < n; i++) {
            if (i == start) continue;
            if (!visited[i] && computers[start][i] == 1) {
                dfs(computers, n, i);
            }
        }
    }
}

• DFS를 활용해서 연결된 모든 컴퓨터를 탐색 후, 방문하지 않았고 연결된 컴퓨터라면 재귀 호출하도록 했다.
• 메인 함수에서는 visited 배열이 false 즉, 방문하지 않은 컴퓨터에 대해서만 dfs() 를 호출하도록 했다.
  • dfs()를 돌면서 연결된 컴퓨터들을 이미 방문했다면 같은 네트워크에 속한 컴퓨터이기 때문이다.
• 즉, dfs() 를 호출한 횟수가 정답이 된다.

두 번째 풀이

// 시간: 0.24ms
// 메모리: 78.8MB

class Solution {
    static boolean[] visited;
    static int[][] computers;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        this.computers = computers;
        visited = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
                answer++;
            }
        }
        
        return answer;
    }
    
    private static void dfs(int now) {
        visited[now] = true;
        for (int i = 0; i < computers[now].length; i++) {
            if (computers[now][i] == 1 && !visited[i]) {
                visited[i] = true;
                dfs(i);
            }
        }
    }
}

• 첫 번째 풀이와 거의 유사하지만, dfs 메서드의 인자를 바꾸었다.
  • 현재 컴퓨터인 now만 인자로 넘겨준다.
  • now와 연결되어 있고(computers[now][i] == 1) 아직 방문하지 않았다면(!visted[i]),
  • 방문처리를 하고, 다시 해당 컴퓨터를 탐색하러 dfs 메서드를 재귀호출한다.
• 시간 복잡도
  • 컴퓨터 개수 : N, 간선 : E
  • computers는 N * N의 인접행렬
  • 인접행렬로 구현한 깊이 우선 탐색은 연결 여부와 상관없이 모드 체크 → O(N^2)