[프로그래머스]43162_네트워크_JAVA 풀이_DFS

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

프로그래머스

개념 _ DFS

	public static void dfs(int[][] adjMatrix,boolean[] visited,int current) {
		
		visited[current] = true;
		System.out.print(current+" ");
		
		for (int j = 0; j < N+1; j++) {
			if(!visited[j] && adjMatrix[current][j] !=0) {
				dfs(adjMatrix,visited,j);	
			}
		}
		
	}

 

풀이

컴퓨터 3개 중 2개가 이어져있고, 1개의 컴퓨터는 이어지지 않았다면 - 네트워크 2개

컴퓨터 3개가 다 이어져있다면 - 네트워크 1개

라는 개념을 잘 이해해야함.

 

• 컴퓨터가 연결된 그래프를 돌면서 1일 때 dfs로 타고 가면서 한 네트워크에 연결된 컴퓨터들은 방문 true처리를 해줌.

 

 

코드

class Solution {
    static int num;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
        num = 0;
        
        /* 모든 컴퓨터를 살펴보며 네트워크에 연결되어있는 컴퓨터는 true처리하며 개수 세기*/
        for(int i=0; i<n;i++){
            if(!visited[i]){
                dfs(n,computers, visited, i);
                num++;
            }
            
        }
        answer = num;
        return answer;
    }
    public void dfs(int n, int[][] computers, boolean[] visited, int i){
        visited[i]=true; 
            
        // 연결되어있다면 타고 들어가기
        for(int j=0;j<n;j++){
            if(computers[i][j]==1 && !visited[j] && j!=i){
                dfs(n,computers,visited,j);
                
            }
        }
        
    }
}