[프로그래머스|JAVA] 네트워크 | ↕️ DFS (깊이 우선 탐색) | 재귀적 방식

[문제 링크]

프로그래머스

[문제]

 

---

 

📍 [코드]

class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];  
        int cnt = 0; 
        
        for (int i = 0; i < n; i++) { 
            if (!visited[i]) {  
                dfs(computers, visited, i);  // DFS로 연결된 컴퓨터 모두 방문
                cnt++;
            }
        }
        
        return cnt;
    }
    
    private void dfs(int[][] computers, boolean[] visited, int node) {
        visited[node] = true; // 현재 노드 방문 처리
        
        for (int i = 0; i < computers.length; i++) {   // 모든 노드와 연결 여부 확인
            if (computers[node][i] == 1 && !visited[i]) {  // 연결되어 있고 아직 방문하지 않았다면
                dfs(computers, visited, i); // 재귀적으로 방문
            }
        }
    }
}

 

💡 접근법

• 각 컴퓨터를 하나씩 돌며
• visited를 true로 설정하여 방문 처리를 하고,
• 연결된 노드가 있는지 확인
  • 이때, 방문하지 않았다면 재귀 호출을 통해 방문하며 연결된 노드 확인
• 호출이 끝난 후 카운트하여 반환

✅ DFS 활용

 

 

---

 

💬 마무리

level 3이라 그런건지,, DFS 문제라 그런건지 상당히 어렵게 느껴졌다ㅠㅠ
레벨도 레벨이지만, 너비 / 깊이 우선 탐색은 내가 약한 부분인 것 같다.
코딩 테스트에서 잘나오는 편인 것 같은데 많은 문제를 풀어보며 적응 해야겠다 !