프로그래머스 | LV.3 네트워크 - DFS, BFS 풀이 (Java)

⬛ 프로그래머스 | LV.3 네트워크 - DFS, BFS 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

문제 설명

---

💚문제 접근 방식

• 연결관계인 computers[][] 배열값을 활용해서 연결된 덩어리 개수가 몇개인지 찾는 문제이다.
• DFS이든, BFS이든 한번 호출할 때 정점들 간의 연결관계를 쭉 탐색하고 반환을 하기 때문에, 네트워크의 개수를 구하기 위해서는 DFS나 BFS 를 활용해서 총 몇 번의 호출로 모든 정점을 순회하는지 확인하면 되는 문제이다. 
• 한 정점으로 쭉 탐색하다가도 단절점이 발견되면 더 이상 방문 불가능해서 반환될 것인데, 여전히 방문 안한 정점이 남아있다면 다시 호출해서 탐색을 시도해야하기 때문이다.

1. 연결 관계를 graph 형태에 담아두고,
2. 방문 체크를 하면서 DFS로 깊이 탐색을 하는데, 호출 횟수 = 연결 덩어리 개수 가 되므로 호출할 때마다 ++ 처리하며 풀었다.

---

• 예전에 DFS, BFS로 모두 풀어본 적 있는 문제이다. 예전 풀이는 여기

프로그래머스 | LV.3 네트워크 문제 (DFS, BFS)

---

💚 제출 코드

import java.util.*;

class Solution {
    static List<ArrayList<Integer>> graph;
    static boolean[] visited;
    
    static void DFS(int val){
        visited[val] = true;
        
        for(int nx : graph.get(val)){
            if(!visited[nx]) {
                DFS(nx);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        visited = new boolean[n];
        
        graph = new ArrayList<>();
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<>());
        }
        
        for(int i=0; i<computers.length; i++){
            for(int j=0; j<computers.length; j++){
                if(computers[i][j] == 1){
                    graph.get(i).add(j);
                }
            }
        }
        
        for(int i=0; i<n; i++){
            if(!visited[i]){
                answer++;
                DFS(i);
            }
        }

        return answer;
    }
}