[프로그래머스] 네트워크 | DFS, BFS | Level.3 | JAVA

📌 문제

 

프로그래머스

 

📒 정답 코드

class Solution {
    
    public void dfs(int node, int[][] computers, boolean[] visit){
        visit[node] = true;
        
        for (int i = 0; i<computers.length; i++){
            if (computers[node][i] == 1 && !visit[i]) {
                dfs(i, computers, visit);
            }
        }        
    }
    public int solution(int n, int[][] computers) {
        boolean[] visit = new boolean[n];
        int count = 0;
        
        for (int i = 0; i<n; i++){
            if (!visit[i]){
                dfs(i, computers, visit);
                count++;
            }
        }
        
        return count;
    }
}

 

⭐ 코드 설명

✅ 방문 기록

DFS는 특정 노드를 시작으로 연결된 모든 노드를 탐색합니다. 여기서 visit 배열은 각 노드가 이미 방문되었는지를 추적합니다.

1️⃣ 메인 반복문에서의 체크

solution 메서드에서 if (!visit[i]) 조건은 현재 노드 i가 방문되지 않았을 때 DFS를 시작하겠다는 의미입니다.

즉, 새로운 네트워크를 발견했을 때 DFS를 호출합니다.

2️⃣ DFS 내부에서의 체크

DFS 내부에서 if (computers[node][i] == 1 && !visit[i]) 조건은 현재 노드(node)와 연결된 노드 i가 방문되지 않았는지를 확인합니다.

이 조건이 없다면, 재귀적으로 이미 방문한 노드를 다시 방문하려 하여, 무한 루프에 빠질 수 있습니다.

📍 정리

• solution 메서드: 네트워크의 시작점을 찾는 역할 (방문하지 않은 노드에서 새로운 DFS 시작).
• dfs 메서드: 특정 노드에서 연결된 노드를 재귀적으로 탐색 (이미 방문한 노드는 다시 탐색하지 않도록 visit 배열 체크).