문제

네트워크

풀이

네트워크가 연결된 개수를 구하는 것이 아니라 노드들이 갖는 네트워크가 몇개 인지를 출력하는 것이다.
1-2가 연결되어있을때 3이 연결되어있지 않다면 전체 네트워크(결과)는 2개 출력 되어야 한다
1-2-3이 연결되어있는 경우에는 전체 네트워크(결과)는 1이 출력되어야 한다

이 부분부터 제대로 이해 하지 못해서 BFS로 풀었을때 제대로 된 값이 나오지 않았다.
그래서 다른 분들의 풀이를 보았는데 DFS로 된 코드가 많아서 DFS 까지 구현하였다.

1. BFS

		Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < computers.length; i++) {
        	// i 번째 컴퓨터가 이미 검사한 컴퓨터 인경우 다음 으로 넘어간다
            if (check[i]) continue;
    		// i 번째 컴퓨터를 검사한다.
            q.add(computers[i]);
            // i 번째는 이미 검사한 컴퓨터이다
            check[i] = true;
            while (!q.isEmpty()) {
                int[] computer = q.poll();
                for (int j = 0; j < computer.length; j++) {
                	// i 번째 컴퓨터가 j 번째 컴퓨터와 연결되어 있고
                    // 이미 검사하지 않았다면 큐에 입력한다.
                    if (!check[j] && computer[j] == 1) {
                        check[j] = true; // 다음에 검사할 컴퓨터는 j 번째 컴퓨터이다.
                        q.add(computers[j]);
                    }
                }
            }
            // i 번째 컴퓨터와 연결된 네트워크가 한개 추가된다.
            result++;
        }

2. DFS

DFS도 BFS와 굉장히 비슷한 풀이로 진행할 수 있다. 위에 것을 재귀로 푸는 것 일 뿐이다.

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

• 해당 부분에서 computers 배열을 전부 돌면서 다음 컴퓨터로 넘어 갈 것인데, 이미 검사한 컴퓨터 인경우에는 다음으로 넘어가게 된다

	/**
     *  DFS
     * @param computers 연결에 대한 정보가 담긴 2차원 배열
     * @param depth 다음에 연결될 컴퓨터 배열
     */
    private static void dfs(int[][] computers, int depth) {
        for (int i = 0; i < computers.length; i++) {
            if (computers[depth][i] == 1 && !check[i]) {
                check[depth] = true;
                dfs(computers, i);
            }
        }
    }

이 부분이 bfs에서 큐 대신 재귀 스택으로 적용 되는 부분이다. 큐는 방문체크를 통해서 반복되는 부분을 체크하여 큐의 개수만큼 반복해주게 되겠지만 스택의 구조를 가지는 재귀는 전부 방문해야 끝나기 때문에 효율성에 있어서는 차이가 있다

전체 코드

전체 코드