[알고리즘] 프로그래머스 네트워크 문제 자바(JAVA)와 DFS로 손쉽게 풀어보자

bfs, dfs 문제는 항상 날 어렵게 하는 문제이다. 해당 유형의 문제에 익숙해지기 위해서는 많은 연습이 필요하다. 꾸준히 열심히 해야겠다….

 

문제

 

아이디어

• 네트워크의 개수는 연결의 시작점과 종점에 의해서 갈라진다. 즉 각 네트워크는 다른 그룹과 독립적이다.
• for문을 통해 순서대로 시작점을 지정한다. 그리고 dfs를 통해 연결점의 종단까지 이동하면서 방문한 노드를 visited 배열을 통해 체크한다.
• 다음 start 점을 선별할 때에는 방문한 노드를 제외하고 네트워크 하나의 dfs가 끝날때마다 네트워크 개수를 count한다.

 

코드

public static int solution(int n, int[][] computers) {
    int answer = 0;

        // 순서대로 탐험하는데 이 때 시작점으로 방문한 노드를 제외한다.
    for (int i = 0; i < n; i++) {
        if (visited[i] == false) {
                        dfs(i,n, computers);
            answer++;
        }
    }
    return answer;
}

// dfs를 통해 종단점까지 이동하면서 방문한 노드를 체크한다.
public static void dfs(int start,int n, int[][] computers) {
        visited[start] = true;

    for (int i = 0; i < n; i++) {
        if(start == i) continue;
        if (computers[start][i] == 1 &&visited[i] == false) {
                    dfs(i,n, computers);
        }
    }
}