[프로그래머스] DFS/BFS - 네트워크 (Java)

프로그래머스 코딩테스트 연습 - (DFS/BFS) 네트워크 (https://programmers.co.kr/learn/courses/30/lessons/43162)

코딩테스트 연습 - 네트워크 | 프로그래머스

이 문제는 DFS를 통해서 해결하면 간단해 보입니다. DFS로 노드를 탐색한 후 dfs 재귀함수가 끝나는 시점에서 다른 노드들을 for문으로 탐색해보면서 방문 안했던 노드가 존재하는지 찾습니다. 만약 방문을 안한 노드가 있다면 또 다른 네트워크가 추가된다는 것을 알 수 있기에 이 기점으로 네트워크 수를 +1 해주면 됩니다.

DFS 알고리즘을 잘 이해하고 계신다면 이번 문제의 코드는 의외로 간단합니다. 풀고나서 다른 분들의 정답지를 봤는데 이번 문제는 다들 거의 비슷하게 해결하셨더라구요! DFS 알고리즘에 대해서는 제가 참고했던 블로그 글을 링크 걸어두겠습니다! 보시고 DFS나 BFS에 대해서 이해하시고 문제 한 번 풀어보세요!

 

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[computers.length];
        
        // Node visit information initialization
        for(int i = 0; i < computers.length; i++){
            visited[i] = false;
        }
        
        for(int i = 0; i < computers.length; i++){
            if(visited[i] == false){
                answer++;
                dfs(i, visited, computers);
            }            
        }
        
        return answer;
    }
    
    public void dfs(int node, boolean[] visited, int[][] computers){
        visited[node] = true;
        
        for(int i = 0; i < computers.length; i++){
            if(visited[i] == false && computers[node][i] == 1){
                dfs(i, visited, computers);
            }
        }
    }
}

 

📌 참고

• DFS 알고리즘 원리에 대한 이해 : https://manducku.tistory.com/23
• java로 구현한 Graph와 DFS 알고리즘 : https://freestrokes.tistory.com/88