[프로그래머스] 네트워크(깊이우선탐색)

프로그래머스

 

DFS(깊이우선탐색)

 

프로그래머스

네트워크

 

문제 정리

1. 컴퓨터들 간의 연결 정보가 주어짐 (인접 행렬 형태)
2. 연결되어 있는 컴퓨터끼리는 같은 네트워크에 속함
3. 네트워크의 개수를 찾아야 함

 

 

시작하기 전 접근 방법

1. 네트워크의 개수를 세기 위해서는 컴퓨터들 간의 연결 상태를 파악해야 함.
2. 각 컴퓨터에 대해 Depth-First Search (DFS)를 사용하여 연결된 컴퓨터를 모두 탐색하면서 하나의 네트워크로 간주해야 한다.
3. 방문한 컴퓨터는 체크하여 중복 방문을 방지하고, 새로운 컴퓨터에 대해 탐색을 시작하여 네트워크의 개수를 증가시킨다.

입출력 예

입출력 예 그림 표현

 

1. 중복 방문 을 check하기 위한 boolean 파입 배열 생성
2. 재귀함수를 이용하여 반복할 수행 작업과 탈출 조건 작성
2-1. 현재 컴퓨터를 시작으로 깊이 우선 탐색을 수행하여 새로운 연결 요소가 발견되면 answer 답 카운트 증가한다.

 

boolean[] check = new boolean[n];
        
for(int i=0;i<n;i++){
	if(!check[i]){
		dfs(computers,i,check);
		answer++;
	}
}

 

 

3. 재귀함수를 이용한 깊이 우선 탐생(DFS) 메서드 생성
3-1. 현재 컴퓨터 확인 check true 변경
3-2. 모든 컴퓨터를 순회하면서 연결된 컴퓨터인지 확인하고 방문하지 않은 컴퓨터 check[]확인이 false라면 연결된 컴퓨터에 대해서 재귀함수 DFS 수행
3-2. dfs 반환 타입이 boolean[]이기 때문에 DFS 완료 후 업데이트돈 check배열을 리턴한다.

boolean[] dfs(int[][] computers, int i, boolean[] check) {
    check[i] = true;

    for (int j = 0; j < computers.length; j++) {
      if (i != j && computers[i][j] == 1 && !check[j]) {
        check = dfs(computers, j, check);
      }
    }
    return check;
  }

 

 

전체 코드

class Solution {
    public int solution(int n, int[][] computers) {
                int answer = 0;
        boolean[] check = new boolean[n];
        
        for(int i=0;i<n;i++){
            if(!check[i]){
                dfs(computers,i,check);
                answer++;
            }
        }


        return answer;
    }
    
  boolean[] dfs(int[][] computers, int i, boolean[] check) {
    check[i] = true;

    for (int j = 0; j < computers.length; j++) {
      if (i != j && computers[i][j] == 1 && !check[j]) {
        check = dfs(computers, j, check);
      }
    }
    return check;
  }
}