547. Number of Provinces

• 한번에 풀지 못했고, intelliJ 를 통해 디버깅을 해야만 했다. 하지만 그렇게 해서라도 해결은 했다. 
• 일단 첫번째 문제는,  정사각형 매트릭스에서 대각선은 전부 1 이기 때문에 대각선의 반쪽만 확인하면 될거라고 생각했는데, 맨 위 row 나 i맨 아래 row 같은 경우는, 맨 왼쪽 혹은 맨 오른쪽에서 시작해야만 자신의 connected node 를 가져올 수 있다. 
• 그래서 0부터  iteration 을 도는데, visited 정보를 따로 관리 하지 않으면 이게 이미 빠진 건지 아닌지를 알 방법이 없다. 그래서 다시 무한루프에 걸렸었다. 
• visited 를 이용하니 해결.
• 성능은 좋지 않다. 
• 4ms  였지만, 25%
• 일단 나의 접근은 set 에 전체 노드를 집어 넣어놓고 꺼내면서, 연관된 node 들을 다 꺼내는 priority queue 를 관리하는 것이었다. 그래서 기존의  set 이 empty 가 되면 종료.

• 일단 내 접근에서 문제점은, 쓸데없이 PQ 를 썼다는 것이다. 아무이유 없이. 그냥 Queue 를 썼어도 되었었다.
• 그리고 실제  node 들을 마치 당구공을 주머니에서 꺼내서 다른 주머니에 넣듯이 했는데. HashSet 으로 visit  을 관리할 필요가 전혀 없이, boolean[n] visited 만으로도 충분했다.
• 그래서 처음부터 각 node 를 Set 에 넣을 필요도, visited 를 set 에 넣을 필요도 없었다.

DFS 로도 접근할 수 있는데, 이렇게 접근한 어떤이의 해결법은 다음과 같다. 아래 풀이를 보고 있자면 사실 그렇게 복잡할 필요도 없었겠다는 생각이 든다.

public int findCircleNum(int[][] isConnected) {
    boolean[] visited = new boolean[isConnected.length];
    int provinces = 0;
    for (int i = 0; i < visited.length; i++) {
        if (!visited[i]) {
            provinces++;
            visit(isConnected, i, visited);
        }
    }
    return provinces;

}

private void visit(int[][] isConnected, int origin, boolean[] visited) {
    if (!visited[origin]) {
        visited[origin] = true;
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[origin][j] == 1) {
                visit(isConnected, j, visited);
            }
        }
    }
}

나처럼 BFS 로 접근 한 다른이의 해결법은 아래와 같다.

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] visited = new boolean[n];
    int count = 0;
    Queue<Integer> queue = new LinkedList<>();

    for (int i = 0; i < n; i += 1) {
        if (visited[i]) {
            continue;
        }
        count += 1;
        queue.add(i);
        visited[i] = true;
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int j = 0; j < n; j += 1) {
                if (j == current || isConnected[current][j] == 0 || visited[j]) {
                    continue;
                }
                queue.add(j);
                visited[j] = true;
            }
        }
    }
    return count;
}