[프로그래머스, LEVEL3] 네트워크

 

컴퓨터의 개수(n)와 컴퓨터간 네트워크 연결 정보(computers)가 주어졌을때 네트워크의 개수를 구하는 문제로 아래의 경우 A와 B가 연결 되어 있고, C는 따로 있으므로 총 네트워크 수는 2개가 된다.

	A	B	C
A	1	1	0
B	1	1	0
C	0	0	1

 

예전에 푼 문제를 다시 보니 전에는 문제를 어떤식으로 풀까 하는 생각을 별로 안하고 풀었던 것 같다.

 

class Solution {
    static int L;
    static boolean flag = false;
    static int[][] ch;

    public int solution(int n, int[][] computers) {
        ch = new int[n][n];
        L = 1;
        for (int i = 0; i < n; i++) {
            flag = false;
            BFS(i, n, computers);
            if (flag)
                L++;
        }
        return L - 1;
    }

    private static void BFS(int i, int n, int[][] computers) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i);
        while (!queue.isEmpty()) {
            int p = queue.poll();
            for (int j = 0; j < n; j++) {
                if (computers[p][j] == 1 && ch[p][j] == 0) {
                    flag = true;
                    ch[p][j] = L;
                    ch[j][p] = L;
                    queue.offer(j);
                }
            }
        }
    }

}

 

다시 푼 코드인데 0 ~ n-1개 컴퓨터를 돌면서 network[] 체크가 안되어있으면 새로운 네트워크로 보고 count를 증가시킨다.

dfs는 해당 컴퓨터에 연결된 다른 컴퓨터를 체크하면서 network[]를 true로 바꾼다.

 

class Solution {
    static boolean[] network;
    static int[][] computers;
    
    public int solution(int n, int[][] computer) {
        computers = computer;
        network = new boolean[n];
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (!network[i]) {
                count++;
            }
            dfs(n, i);
        }
        
        return count;
    }
    
    private void dfs(int n, int i) {
        network[i] = true;
        
        for (int j = 0; j < n; j++) {
            if (!network[j] && computers[i][j] == 1) {
                dfs(n, j);
            }
        }
    }
}

 

 

프로그래머스