LeetCode (C/C++, Java) 547. Number of Provinces

https://leetcode.com/problems/number-of-provinces/description/

---

풀이

모든 노드를 탐색하며 아직 방문하지 않았다면 해당 노드와 연결된 노드들을 순회한 후 province의 수를 증가한다.

---

C/C++ 코드

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        bool visited[200] = {0, };
        int cnt = 0;
        int n = isConnected.size();
        queue<int> q;

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            q.push(i);
            visited[i];
            while (!q.empty()) {
                int now = q.front();
                q.pop();

                for (int j = 0; j < n; j++) {
                    if (i == j || !isConnected[now][j] || visited[j]) continue;
                    q.push(j);
                    visited[j] = true;
                }
            }
            cnt++;
        }
        return cnt;
    }
};

 

Java 코드

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, answer = 0;
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (isConnected[i][i] < 0) continue;

            isConnected[i][i] = -1;
            q.add(i);
            while (q.isEmpty() != true) {
                int now = q.poll();
                for (int j = 0; j < n; j++) {
                    if (i != j && isConnected[now][j] > 0) {
                        q.add(j);
                        isConnected[now][j] = -1;
                        isConnected[j][now] = -1;
                    }
                }
            }
            answer++;
        }
        return answer;
    }
}