[프로그래머스] 네트워크 자바

문제

 

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

 

 

문제풀이

 

이 문제는 쉬워서 그런진 몰라도 DFS문제치고 굉장히 빨리 풀어서 기쁘다,,ㅎㅎ

컴퓨터로 주어지는 배열을 노드로 보고, 노드를 차례차례 방문하여 연결되어 있는 끝까지 가서 방문 여부를 표시하면 되기 때문에 이 문제도 DFS로 구현하면 된다.

 

처음 0번 노드부터 시작하여 연결된 노드(1표시)를 탐색하여 visted배열에 표시한다 (computers 열의 값 확인)

그리고 끊기면 visited배열 중에서 아직 방문안된(false표시인) 노드부터 다시 dfs를 실행한다.

 

 

 

소스코드

 

class Solution {
    static boolean[] visited;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        visited = new boolean[n];  // 방문받을 배열
        
        for(int i = 0; i < n; i++){
            if(visited[i] == false){
                dfs(i, computers, n);
                answer++;
            }
        }
        return answer;
    }
    
    public void dfs(int start, int[][] computers, int n) {
        if(visited[start] == true)  	//이미 방문된 정점이라면
            return;
        else
            visited[start] = true;
       
        for(int i = 0; i < n; i++){		 		// 시작정점의 연결된 정점을 하나하나 보고
            if(i != start && computers[start][i] == 1){ 	// 자기자신이 아니고 연결되어있으면
                dfs(i, computers, n);   			// 그 연결정점으로 다시 탐색
            }
        }
        
    }
}