[DAY77] Algorithm: Network Connection

이 문제는 컴퓨터 간의 연결 정보를 바탕으로 독립된 네트워크(연결 요소)의 개수를 구하는 문제다. 그래프 탐색 알고리즘인 DFS(깊이 우선 탐색)를 사용하여, 방문하지 않은 노드에서 시작해 연결된 모든 노드를 방문 처리하는 방식으로 해결했다. 특히 C++에서 재귀 함수 사용 시 참조자(&)를 통해 메모리를 효율적으로 관리하는 것이 중요하다.

---

❓ 문제 분석

• 목표: 컴퓨터의 개수 $n$과 연결 정보 computers 배열이 주어질 때, 총 네트워크의 개수를 return 해야 한다.
• 제약 조건: 컴퓨터의 개수 $n$은 1 이상 200 이하. ($n$이 작기 때문에 $O(n^2)$ 복잡도도 충분히 통과 가능하다.)
• 핵심 키워드: "A와 B가 연결, B와 C가 연결되면 A와 C도 연결" $\rightarrow$ 그래프의 연결 요소(Connected Component)

---

💡 풀이 설계

1. 시도했던 접근 (First Attempt)

• 처음에는 단순한 선형 탐색이나 반복문으로 해결할 수 있을까 고민했다.
• 하지만 "간접적으로 연결된 것"도 같은 네트워크로 봐야 한다는 점에서, 한 노드를 잡고 끝까지 파고드는 탐색이 필요함을 깨달았다.

2. 최종 해결책 (Solution)

• DFS(깊이 우선 탐색)를 사용하여 연결된 덩어리를 찾기로 결정했다. (BFS도 가능하지만 재귀로 구현하는 게 코드가 더 간결해 보였다.)
• 예상 시간 복잡도: $O(n^2)$
  • 모든 노드를 한 번씩 방문($n$) $\times$ 각 노드별로 연결된 노드 확인($n$)
• 알고리즘 흐름:
  1. 방문 여부를 저장할 visited 배열을 false로 초기화한다.
  2. 모든 컴퓨터($0$ ~ $n-1$)를 순회한다.
  3. 만약 아직 방문하지 않은 컴퓨터라면? 새로운 네트워크 발견! (answer++)
  4. 그 컴퓨터를 시작점으로 DFS를 호출하여 연결된 모든 친구들을 찾아 visited를 true로 바꾼다.

---

💻 코드 구현

#include <vector>
#include <iostream>

using namespace std;

// DFS 함수: 현재 컴퓨터(i)와 연결된 모든 컴퓨터를 찾아 방문 처리한다.
// 중요: vector를 넘길 때 복사를 방지하고 원본을 수정하기 위해 참조자(&)를 사용해야 한다.
void DFS(int i, vector<vector<int>>& computers, vector<bool>& visited, int n) {
    visited[i] = true; // 현재 노드 방문 처리
    
    // 모든 컴퓨터를 돌면서 연결되어 있는지 확인
    for (int j = 0; j < n; ++j) {
        // 1. i와 j가 연결되어 있고 (computers[i][j] == 1)
        // 2. j를 아직 방문하지 않았다면 (visited[j] == false)
        if (computers[i][j] == 1 && visited[j] == false) {
            DFS(j, computers, visited, n); // 더 깊이 탐색 (재귀)
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false); // 방문 기록용 배열
    
    // 모든 컴퓨터를 순차적으로 확인
    for (int i = 0; i < n; ++i) {
        // 방문하지 않은 컴퓨터가 있다면 새로운 네트워크의 시작점이다.
        if (visited[i] == false) {
            DFS(i, computers, visited, n); // 연결된 모든 컴퓨터 방문 처리
            answer++; // 네트워크 개수 증가
        }
    }
    
    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: 처음에 DFS 함수의 매개변수를 void DFS(int i, vector<vector<int>> computers, ...) 형태로 작성하려 했다.
• 원인: C++에서는 이렇게 쓰면 배열이 값 복사(Call by Value)가 일어난다. 즉, 함수 안에서 visited를 아무리 바꿔도 밖에서는 바뀌지 않고, 메모리도 엄청 낭비된다.
• 해결: vector<...>& 처럼 참조자(&)를 붙여서 원본 데이터를 직접 수정하도록 변경했다. 이걸 놓치면 시간 초과나 로직 오류가 발생할 수 있다.

---

✅ 오늘의 회고

항목	내용
유형	Graph, DFS/BFS
체감 난이도	중 (개념 잡는 게 중요했음)
복잡도	시간: $O(n^2)$, 공간: $O(n)$ (재귀 스택 + visited 배열)
새로 배운 것	연결 요소의 개념, C++에서 vector를 함수 인자로 넘길 때 꼭 &를 붙여야 한다는 점!