[프로그래머스/Java] Lv.3 - 네트워크

📝 문제 설명

컴퓨터들이 서로 연결되어 있을 때, 형성된 독립적인 네트워크의 총 개수를 구하는 문제입니다. A와 B가 연결되어 있고 B와 C가 연결되어 있다면 A, B, C는 모두 하나의 네트워크에 속합니다.

---

💡 접근 방식

1. 그래프 탐색 선정

연결된 모든 정점을 끝까지 파고드는 DFS(깊이 우선 탐색) 방식을 선택했습니다. 하나의 노드를 방문했을 때 그와 연결된 모든 노드를 연쇄적으로 방문 처리함으로써 하나의 '네트워크' 덩어리를 식별할 수 있습니다.

2. 방문 배열(visit) 관리

컴퓨터의 수만큼 boolean[] visit 배열을 생성했습니다.

• 아직 방문하지 않은 컴퓨터를 발견하면 새로운 네트워크가 시작된 것이므로 answer를 1 증가시킵니다.
• 해당 컴퓨터를 시작점으로 DFS를 수행하여 연결된 모든 컴퓨터를 방문 완료 상태로 바꿉니다.

3. DFS 로직

computers[now][i] == 1인 경우(연결된 경우)이면서 아직 방문하지 않은(!visit[i]) 컴퓨터를 찾으면 재귀적으로 탐색을 이어갑니다. 이때 자기 자신(i == now)은 제외하도록 예외 처리를 했습니다.

---

💻 구현 코드

import java.util.*;

class Solution {
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        boolean[] visit = new boolean[n];
        
        for(int i=0; i<n; i++) {
            if(!visit[i]) {
                dfs(computers, visit, i, n);
                answer++;
            }
        }
        
        return answer;
    }
    
    public void dfs(int[][] computers, boolean[] visit, int now, int n) {
        visit[now] = true;
        
        for(int i=0; i<n; i++) {
            if(i == now) continue;
            if(visit[i]) continue;
            if(computers[now][i] == 1) {
                dfs(computers, visit, i, n);
            }
        }
    }
}

---

✨ 느낀 점

• DFS의 정석: 그래프의 연결 요소 개수를 찾는 전형적인 패턴을 익힐 수 있었습니다.

• 재귀의 흐름: 재귀 함수가 호출되면서 방문 배열이 어떻게 업데이트되는지 머릿속으로 그려보는 과정이 큰 도움이 되었습니다.

• BFS와의 비교: 이 문제는 BFS로도 충분히 해결 가능하지만, 연결된 덩어리를 찾는 데에는 DFS가 코드가 더 간결하다는 점을 느꼈습니다.