[PG] 네트워크 JAVA

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

노드의 개수 int n, 노드 간 연결상태를 인접행렬로 나타낸 int[][] computers 가 주어진다.

 

component의 개수를 반환해야한다.

 

 

 

풀이 1.

import java.util.*;

class Solution {
    boolean[] check = null;

    public void dfs(int node, int[][] computers) {
        check[node] = true;

        for(int i = 0; i < computers[node].length; i++) {
            if(computers[node][i] == 1 && check[i] == false) {
                dfs(i, computers);
            }
        }
    }

    public void bfs(int start, int[][] computers) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);

        while(!que.isEmpty()) {
            int node = que.poll();
            for(int i = 0; i < computers[node].length; i++) {
                if(computers[node][i] == 1 && check[i] == false) {
                    que.add(i);
                    check[i] = true;
                }
            }
        }
    }


    public int solution(int n, int[][] computers) {
        int answer = 0;
        check = new boolean[computers.length];

        for(int i = 0; i < computers.length; i++) {
            if(check[i] == false) {
                dfs(i, computers);
//                bfs(i, computers);
                answer++;
            }
        }

        return answer;
    }
}

주어진 인접행렬을 그대로 사용했다.

 

 

 

풀이 2.

import java.util.*;

class Solution {
    ArrayList<Integer>[] list = null;
    boolean[] check = null;

    public void dfs(int node) {
        check[node] = true;

        for (int i = 0; i < list[node].size(); i++) {
            int next = list[node].get(i);
            if (check[next] == false) {
                dfs(next);
            }
        }
    }

    public void bfs(int start) {
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(start);
        check[start] = true;

        while (!que.isEmpty()) {
            int node = que.poll();
            for (int i = 0; i < list[node].size(); i++) {
                int next = list[node].get(i);
                if (check[next] == false) {
                    que.add(next);
                    check[next] = true;
                }
            }
        }
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;
        list = new ArrayList[n + 1];
        check = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < computers.length; i++) {
            for (int j = 0; j < computers[i].length; j++) {
                if (computers[i][j] == 1) {
                    list[i + 1].add(j + 1);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (check[i] == false) {
                dfs(i);
// 				bfs(i);
                answer++;
            }
        }

        return answer;
    }
}

인접리스트로 고쳐서 풀 수도 있다.

 

 

 

 

 

전형적인 DFS, BFS 문제라 딱히 쓸 말이 없다.