[Leetcode] 547. Number of Provinces 문제 풀이

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

Number of Provinces - LeetCode

 

문제 내용

서로 연결된 노드를 하나의 province라고 하고,

province의 갯수를 구하는 문제

 

Example 1:

예제1번 그림

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output: 2

 

문제 풀이

dfs를 이용해서 서로 연결된 노드를 방문 할 수 있다.

방문된 노드는 다시 방문하지 않게 따로 체크해야 한다.

class Solution {
public:
    bool visit[200] = {false};
    int n;
    
    void dfs(vector<vector<int>>& isConnected, int u) {
        visit[u] = true;
        
        for (int v = 0; v < n; ++v) {
            if (visit[v] || isConnected[u][v] == 0)
                continue;
            
            dfs(isConnected, v);
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        n = isConnected.size();
        
        int num = 0;
        for (int i = 0; i < n; ++i) {
            if (!visit[i]) {
                dfs(isConnected, i);
                ++num;
            }
        }
        return num;
    }
};