[43162] 네트워크

✔ 네트워크

[프로그래머스 43162]

문제 분석하기

깊이 우선 탐색을 진행하면서 같은 네트워크로 연결될 수 있는지 확인

같은 네트워크로 연결될 수 없다면 연결되지 않은 컴퓨터 중 하나를 골라 다시 연결 반복

손으로 풀어보기

1. 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행
   • DFS를 실행할 때 현재 노드에서 연결된 노드라면 네트워크 개수 증가 X
   • 새롭게 시작되는 DFS라면 네트워크 개수 증가 O
2. 네트워크 개수 반환

슈도코드 작성하기

n(컴퓨터의 개수)
computers(연결에 대한 정보가 담긴 2차원 배열)
visited(방문 기록 저장 배열)
answer(네트워크 개수)
for(n만큼 반복하기) {
    if(방문하지 않았다면) {
        DFS(n)
        answer 증가
    }
}
answer 반환

DFS {
    visited 배열에 현재 노드 방문 기록하기
    if(현재 노드의 연결 노드 중 방문하지 않은 노드로) {
        DFS 실행하기 (재귀 형태)
    }
}

코드 구현하기

/**
 * 43162) 네트워크
 */
public class K002_43162 {
    // visited(방문 기록 저장 배열)
    static boolean[] visited;

    // n(컴퓨터의 개수)
    // computers(연결에 대한 정보가 담긴 2차원 배열)
    public int solution(int n, int[][] computers) {
        visited = new boolean[n + 1];
        // answer(네트워크 개수)
        int answer = 0;
        for (int i = 0; i < n; i++) {
            // 방문하지 않았다면
            if (!visited[i]) {
                // 각 컴퓨터에서 DFS 실행
                DFS(computers, i);
                // answer 증가
                answer++;
            }
        }
        // answer 반환
        return answer;
    }

    // DFS
    private void DFS(int[][] computers, int node) {
        // visited 배열에 현재 노드 방문 기록하기
        visited[node] = true;
        // 현재 노드의 연결 노드 중 방문하지 않은 노드로
        for (int next = 0; next < computers.length; next++) {
            if (visited[next] == false) {
                if (computers[node][next] == 1)
                    // DFS 실행하기 (재귀 형태)
                    DFS(computers, next);
            }
        }
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K002_43162 solution = new K002_43162();

        int n = 3;
        int[][] computers = { { 1, 1, 0 }, { 1, 1, 0 }, { 0, 0, 1 } };

        int result = solution.solution(n, computers);

        System.out.println(result);
    }
}