난이도

Level 3

문제

문제 바로가기

문제 검토

대놓고 그래프를 줘서 탐색만 하면 되는걸로 보이는데 왜 Level3인지는 모르겠다.
놓친 변수가 있을 수도 있으나 일단 DFS로 풀어보자

풀이

아이디어

//연결되어 있는 노드를 출구 없이 그냥 탐색만 하면 되므로 DFS가 더 적절해보인다.
//DFS를 돌릴 때마다 answer+1을 해주면 될 것 같다.

JAVA

class Solution {
    static boolean[] visited;
    public int solution(int n, int[][] computers) {        
        int answer = 0;
        visited=new boolean[n+1];        
        for(int i=0;i<n;i++){
            visited[i]=false;
        }
        for(int i=0;i<n;i++){
            if(!visited[i]){
                dfs(i,n,visited,computers);    
                answer+=1;
            }
        }
        
        return answer;
    }
    public void dfs(int idx,int n,boolean[] visited,int[][] computers){
        if(visited[idx] == true){
            return;
        }
        visited[idx]=true;
        for(int i=0;i<n;i++){
            if(computers[idx][i]==0){
                continue;
            }
            if(idx==i){
                continue;
            }
            dfs(i,n,visited,computers);
        }
    }
}

DFS로 풀이했다.

걸린 시간

16:58

총평

코테라고 생각하고 풀었다.
백준 기준 실버1 정도의 문제라고 생각한다.