프로그래머스-네트워크 JAVA DFS/BFS

역시 dfs/bfs문제는 아이디어 떠올리는게 제일 어렵다..

 

1) visit으로 방문한 곳/방문하지 않은 곳을 체크해준다

2) 이어져있는 것들은 한번만 answer을 증가시키면서 visit은 모든 노드에 체크를 해줘야한다

3) dfs에서 들어오면 무조건 visit을 true로 바꿔줌

  -> 방문하지 않은 것중에 이어져있는것(computers[index][i]가 1인것)을 찾아서 체크해주면 된다

  -> 이때 자기 자신도 패스

4) answer++은 처음 for문에서 dfs를 벗어났을 때만! ++해줌

 

연습 좀 더 많이 해야겠다...

 

class Solution {
    public int dfs(int index, boolean[] visit, int[][] computers){
        visit[index]=true;
        for(int i=0;i<computers.length;i++){
            if(i!=index && (!visit[i])&& computers[index][i]==1){
                dfs(i, visit, computers);
            }
        }
        return 0;
    }
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean visit[]=new boolean[computers.length];
        
        for(int i=0;i<computers.length;i++){
            if(!visit[i]){
                dfs(i, visit, computers);
                answer++;
                }
        }
        return answer;
    }
}