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

💡 문제
네트워크(https://school.programmers.co.kr/learn/courses/30/lessons/43162)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

그래프 이론

• 그래프는 노드(또는 정점)와 간선으로 이루어진 자료 구조입니다. 노드는 개체나 개념을 나타내고, 간선은 이러한 노드들 간의 관계를 나타냅니다.
• 그래프는 방향성이 있는 유향 그래프와 방향성이 없는 무향 그래프로 나뉩니다.
• 컴퓨터 네트워크 문제에서는 주로 무향 그래프를 다루며, 연결된 노드들의 집합을 찾는 문제로 해석됩니다.

그래프 탐색

• 그래프 탐색은 그래프 내의 모든 노드를 방문하는 알고리즘입니다. 대표적으로 DFS와 BFS가 있습니다.
• DFS(깊이 우선 탐색)는 한 노드에서 시작하여 그래프의 최대 깊이까지 탐색한 후, 다시 돌아와 다른 경로를 탐색합니다.
• BFS(너비 우선 탐색)는 한 노드에서 시작하여 인접한 모든 노드를 탐색한 후, 다음 단계의 인접한 노드들을 탐색합니다.

인접 행렬과 인접 리스트

• 그래프를 표현하는 방법으로 인접 행렬과 인접 리스트가 있습니다.
• 인접 행렬은 2차원 배열로 그래프를 표현하며, 각 요소는 노드들 간의 연결 여부를 나타냅니다.
• 인접 리스트는 리스트나 링크드 리스트로 그래프를 표현하며, 각 노드의 인접한 노드들을 리스트로 저장합니다.

시간 복잡도와 공간 복잡도

• 알고리즘의 효율성을 평가하는 데 사용되는 지표입니다.
• 시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 나타내며, 주로 빅 오 표기법으로 표현됩니다.
• 공간 복잡도는 알고리즘이 사용하는 메모리의 양을 나타내며, 빅 오 표기법으로 표현됩니다.

---

🤓 문제 풀이

🔨 문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

이 문제는 주어진 컴퓨터의 연결 정보를 바탕으로 네트워크의 개수를 찾는 문제입니다. 네트워크란 연결된 컴퓨터들의 집합으로 정의됩니다. 따라서 주어진 그래프에서 연결된 컴포넌트(네트워크)의 개수를 찾는 것이 목표입니다.

---

🔨 접근 방법

• 그래프 표현:
  • 컴퓨터가 노드이고, 연결이 엣지인 그래프 구조로 해석할 수 있습니다.
  • 각 컴퓨터는 그래프의 노드로, 각 연결은 그래프의 엣지로 볼 수 있습니다. 주어진 2차원 배열 computers는 인접 행렬로 표현된 그래프입니다.
  • 문제에서 컴퓨터 간의 연결을 2차원 배열로 주어졌습니다. 이 배열은 인접 행렬로 그래프를 표현한 것입니다.
• 연결된 컴포넌트 찾기:
  • 문제는 주어진 그래프에서 서로 연결된 컴퓨터 그룹, 즉 연결된 컴포넌트의 개수를 찾는 것입니다.
  • DFS(또는 BFS)는 그래프에서 연결된 컴포넌트를 탐색하는 데 효율적인 알고리즘입니다.
  • 각 노드를 방문하고, 방문한 노드와 연결된 모든 노드를 재귀적으로 방문함으로써 하나의 컴포넌트를 완전히 탐색할 수 있습니다.
• 재귀적 탐색 필요성:
  • 컴퓨터가 서로 연결되어 있는지 확인하려면, 각 노드에서 시작하여 연결된 모든 노드를 방문해야 합니다.
  • DFS는 스택 구조를 사용하여 깊이 우선으로 탐색하며, 이를 재귀적으로 구현하면 직관적이고 간단하게 그래프를 탐색할 수 있습니다.
• DFS 탐색:
  • DFS를 사용하여 각 노드를 방문할 때마다 visited 배열을 업데이트하여 방문 여부를 추적할 수 있습니다.

---

🔨 문제 풀이 과정

• 그래프 구성:
  • 인접 행렬을 사용하여 주어진 컴퓨터의 연결 정보를 그래프로 표현합니다.
  • 이 그래프를 기반으로 DFS를 수행합니다.
• DFS 탐색:
  • 모든 노드를 한 번씩 방문하며, 방문한 노드는 다시 방문하지 않아야 합니다.
  • 각 노드가 방문되었는지 방문 여부를 확인하기 위한 visited 배열을 초기화합니다.
  • 각 컴퓨터를 시작점으로 DFS를 수행하여 연결된 모든 컴퓨터를 방문합니다.
  • DFS를 사용하여 하나의 노드에서 시작해 연결된 모든 노드를 방문합니다. DFS가 끝난 후에는 하나의 네트워크가 모두 방문된 것이므로 네트워크 카운트를 증가시킵니다.
• 네트워크 개수 반환:
  • 모든 컴퓨터를 탐색한 후에는 네트워크의 개수를 반환합니다.

---

🔨 DFS 선택 이유

이 문제는 네트워크의 개수를 구하는 문제입니다. 이 문제를 풀기 위해서는 여러 컴퓨터가 어떻게 연결되어 있는지를 알아야 하며, 이 연결된 컴퓨터들 간의 관계를 탐색하는 방법이 필요합니다.

DFS(Depth-First Search)는 그래프의 모든 노드를 탐색하는 데 효과적입니다. 특히, 연결된 네트워크를 찾는 문제에서는 DFS를 사용하면 간단하고 직관적인 해결책을 얻을 수 있습니다. DFS를 통해 하나의 노드를 방문하면 그와 연결된 모든 노드를 방문하게 되어, 하나의 네트워크를 탐색하는 데 적합합니다.

---

🔨 구현코드

class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n]; // 각 컴퓨터의 방문 여부를 저장하는 배열
        int networkCount = 0; // 네트워크의 개수를 저장할 변수
        
        for (int i = 0; i < n; i++) { // 모든 컴퓨터에 대해 반복
            if (!visited[i]) { // 아직 방문하지 않은 컴퓨터인 경우
                dfs(i, visited, computers); // DFS 탐색을 수행하여 연결된 컴퓨터들을 모두 방문
                networkCount++; // 네트워크 개수를 증가시킴
            }
        }
        
        return networkCount; // 최종적으로 찾은 네트워크의 개수 반환
    }
    
    private void dfs(int computer, boolean[] visited, int[][] computers) {
        visited[computer] = true; // 현재 컴퓨터를 방문 처리
        
        for (int i = 0; i < computers.length; i++) { // 현재 컴퓨터와 연결된 모든 컴퓨터에 대해 반복
            if (computers[computer][i] == 1 && !visited[i]) { // 연결되어 있고, 아직 방문하지 않은 컴퓨터인 경우
                dfs(i, visited, computers); // 해당 컴퓨터에서 다시 DFS 탐색 수행
            }
        }
    }
}

---

📚 풀이 보완

코드 설명

1. 초기화:
   • visited 배열은 모든 컴퓨터를 방문했는지 여부를 추적합니다.
   • networkCount는 네트워크의 개수를 세기 위한 변수입니다.
2. for 루프를 통한 DFS 탐색:
   • 각 컴퓨터를 방문하면서, 방문하지 않은 컴퓨터를 발견하면 그 컴퓨터를 시작점으로 DFS를 수행합니다.
   • DFS가 끝나면 하나의 네트워크가 완전히 탐색된 것이므로 networkCount를 증가시킵니다.
3. DFS 구현:
   • 현재 컴퓨터를 방문 처리한 후, 현재 컴퓨터와 직접 연결된 다른 컴퓨터들을 찾아 방문하지 않은 컴퓨터에 대해 재귀적으로 DFS를 호출합니다.

이 코드의 시간 복잡도는 O(n^2)로, 이는 주어진 문제의 제한 사항 내에서 효율적으로 작동합니다. DFS를 통해 모든 노드를 방문하여 연결된 컴포넌트를 찾기 때문에, 네트워크의 개수를 정확하게 세는 데 적합합니다.

---

📍 Plus+

공간 복잡도

• 주어진 문제에서 사용한 공간(메모리)의 양을 나타냅니다. 이 문제의 공간 복잡도는 O(n^2)입니다. 이는 인접 행렬을 저장하는 데 필요한 공간과 방문 여부를 저장하는 visited 배열이 n의 크기를 갖기 때문입니다. 인접 행렬을 저장하는데 O(n^2)의 공간이 필요하며, 방문 여부를 나타내는 visited 배열도 O(n)의 공간이 필요합니다. 따라서 전체 공간 복잡도는 O(n^2)입니다.

시간복잡도

• 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 나타냅니다. 이 문제의 시간 복잡도는 O(n^2)입니다. DFS 알고리즘을 사용하여 그래프를 탐색하므로, 최악의 경우 모든 노드를 한 번씩 방문하고 각 노드에서 연결된 모든 노드를 확인해야 합니다. 그렇기 때문에 n^2의 시간이 소요됩니다.

요약

• 공간 복잡도 : O(n^2)
• 시간 복잡도 : O(n^2)

---

문제를 풀기위한 고민

BFS(너비 우선 탐색) 알고리즘

BFS를 사용하여 네트워크의 개수를 찾는 방법은 DFS와 유사합니다. 다만, DFS가 스택을 사용하여 깊이 우선으로 탐색하는 반면, BFS는 큐를 사용하여 너비 우선으로 탐색합니다. 각 연결된 노드를 방문할 때마다 해당 노드를 큐에 추가하여, 해당 노드와 연결된 모든 노드를 탐색합니다. BFS를 사용하여 문제를 해결할 경우 시간 복잡도는 여전히 O(n^2)이 됩니다.

 

수학적 접근 방식

수학적으로 접근하여 문제를 해결하는 방법도 가능합니다. 이 경우 연결된 그래프의 특성을 고려하여 문제를 해결합니다. 네트워크 문제는 전체 그래프에서 연결된 부분 그래프를 찾는 문제이므로, 그래프 이론의 다양한 정리와 알고리즘을 적용할 수 있습니다. 예를 들어, 그래프 이론에서 사용되는 컴포넌트 분리 알고리즘 등을 활용하여 네트워크의 개수를 찾을 수 있습니다.

 

선택적인 알고리즘 사용 및 수학적 접근 방식

네트워크 문제는 그래프 이론에서 다양한 접근 방식을 사용할 수 있는 문제입니다. DFS와 BFS는 그래프 탐색에 가장 일반적으로 사용되는 알고리즘 중 하나이지만, 수학적 접근 방식을 사용하여 문제를 해결할 수도 있습니다. 알고리즘 선택은 문제의 특성과 개발자의 선호도에 따라 달라질 수 있습니다. 종종 여러 가지 접근 방식을 시도하고 비교하여 가장 효율적인 방법을 선택하는 것이 좋습니다.