1. 문제 설명

• n개의 컴퓨터가 있을 때, 컴퓨터들이 연결되어 있는 정보를 담은 2차원 배열이 주어짐.
• 연결된 컴퓨터들을 하나의 네트워크로 간주할 때 총 네트워크의 개수를 반환해야 함.

// [input]
 n (1 ≤ n ≤ 200) : 컴퓨터의 개수
computers (n × n 배열): 연결된 컴퓨터들에 대한 정보. (1: 연결)

2. 스크래치

풀이: 그래프 탐색 (DFS)

• 각 컴퓨터(노드)에서 연결된 다른 컴퓨터들을 재귀적으로 방문함.

1. 모든 컴퓨터를 순회하면서 아직 방문하지 않은 컴퓨터라면
   → 먼저 네트워크 수를 ++
   → 그 컴퓨터와 연결된 컴퓨터를 dfs 함수를 호출하면서 모두 방문 처리하여 같은 네트워크로 묶음
2. 메인 반복문으로 돌아가 아직 방문하지 않은 컴퓨터가 있다면
   → 네트워크 수 ++
   → dfs로 같은 네트워크로 묶는 과정을 반복

3. 코드

class Solution {
    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]) { // 아직 방문하지 않은 컴퓨터면
                answer++; // 네트워크 개수 추가
                dfs(i, visited, computers, n); // 연결된 모든 컴퓨터 찾기
            }
        }
        return answer;
    }

		// dfs: 연결된 컴퓨터 방문 처리
    void dfs(int current, boolean[] visited, int[][] computers, int n) {
        visited[current] = true; // 현재 컴퓨터 방문 처리

	       // 현재 컴퓨터와 연결된 다른 컴퓨터 체크 
        for (int i = 0; i < n; i++) {
            if (computers[current][i] == 1 && !visited[i]) {
                dfs(i, visited, computers, n); // 그 컴퓨터로 이동 -> 다시 연결 확인
            }
        }
    }
}

4. De-fault

시간 복잡도

• DFS 시간 복잡도: O(n^2) (n: 컴퓨터 수)

개선 방향

• Union-Find 방식을 사용하면 네트워크의 개수를 세는 작업을 더 빠르게 할 수 있음
  이 방법은 O(n)에 가까운 시간 복잡도로 해결할 수 있으며, 트리 구조로 연결을 관리하기 때문에 탐색 속도가 빠름.

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요.
알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂