[JAVA] 프로그래머스 : 네트워크 (코딩테스트 고득점 kit > 깊이/너비 우선 탐색(DFS/BFS))

https://programmers.co.kr/learn/courses/30/lessons/43162?language=java

코딩테스트 연습 - 네트워크

문제 이해

문제의 예시를 보면 왼쪽의 그림은 네트워크가 2개인 경우이고 오른쪽의 그림은 네트워크가 1개인 경우임

즉, n개의 컴퓨터들이 있고 연결되어있는 컴퓨터들이 각각의 네트워크임

따라서 DFS를 통해 연결되어있는 컴퓨터들끼리 네트워크를 구성하므로 네트워크의 갯수를 구해주는 문제임 

 

해결 방안

1. solution() 에서 전체 컴퓨터들의 방문 여부를 따져주고 방문되지 않은 컴퓨터의 경우 dfs()를 통해 연결된 컴퓨터들을 방문됬다고 표시되면 하나의 네트워크가 구성된다. 하나의 네트워크가 구성되면 answer 값을 증가해줌 

2. dfs() 에서는 해당 방문 컴퓨터를 방문했다고 체크해주고 인접 컴퓨터를 돎
이 때 인접 컴퓨터 여부는 computers에 저장되있는 값을 이용함(1이면 인접 컴퓨터)
인접한 컴퓨터이면서 방문한적 없으면 dfs()를 해줌

 

코드

// 네트워크
class Solution {
    public static int answer = 0;
    public static boolean[] visited;
    
    public static void dfs(int start, int[][] computers){
        visited[start] = true;
        
        // 인접 노드 돌기
        for(int i=0; i<computers[start].length; i++){
            // 자기는 제외
            if(i==start)
                continue;
            // 인접한 노드 아니여도 제외
            if(computers[start][i] == 0)
                continue;
            // 인접한 노드 
            else{
                // 방문한 적 없으면 dfs
                if(visited[i] == false)
                    dfs(i, computers);
            }
        }
    }
    
    // n: vertex , computers: edge
    public int solution(int n, int[][] computers) {
        
        visited = new boolean[n];
        for(int i=0; i<visited.length; i++){
            visited[i] = false;
        }
        
        // i는 start
        for(int i=0; i<visited.length; i++){
            // 방문한 적이 없으면 dfs
            if(visited[i] == false){
                dfs(i, computers);
                answer++;
            }
        }
        
        return answer;
    }
}