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

DFS 연습하는 문제

 

 DFS 시 항상 생각해야 할 문제

  1. 탈출 조건을 어떻게 만들 지

  2. DFS 라면 깊이를 어떻게 끝까지 도달하게 할 지

  3. 예외 사항 처리 어떻게 할 지

 순서로 고민해보자.

 

 - 네트워크에서의 탈출조건

  1. 모든 네트워크 지점 체크 완료 (예 1,2,3 이 있다면 노드 1,2,3 체크 완료)

  2. 네트워크가 연결될 경우 끝까지 도달하고 도달했다면 false 리턴 ( 체크한 노드들은 모드 0 = false 로 바꿔주기)

  3. 예외 사항 처리 ( 없음)

 

class Solution {
    static Boolean dfs(int[][] computers,int n) {
        if(computers[n][n] == 0) {
            return false;
        }
        computers[n][n] = 0;
        for(int i=0;i<computers.length;i++) {
            if(computers[n][i] > 0) {
                dfs(computers, i);
            }
        }
        return true;
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        for(int i=0; i< n; i++) {
            if(computers[i][i] > 0 && dfs(computers, i)) {
                answer++;
            }
        }
        return answer;
    }
}