Leetcode - 547. Number of Provinces

문제

각 도시의 연결 관계가 그래프의 인접행렬 형식으로 주어진다. 연결되어있는 모든 도시를 하나의 Province라고 할때, 총 Province의 갯수는?

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

해결 아이디어

각 노드별로 백트래킹 형태의 dfs 순회를 한다.

해결

인접행렬의 DFS순회 코드 다시 살펴보기.

class Solution {
    vector<int> visit; // node already visited
    void mark_connection(vector<vector<int>>& graph, int from) {
        for (int i = 0; i < graph[from].size(); i++) {
            if (graph[from][i] == 0 || visit[i] == 1)
                continue;
            visit[i] = 1;
            mark_connection(graph, i);
        }
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int rsize = isConnected.size();
        visit = vector<int>(rsize, 0);
        int nr_province = 0;
        
        for (int i = 0; i < rsize; i++) {
            if (visit[i] == 1)
                continue;
            mark_connection(isConnected, i);
            nr_province++;
        }
        return nr_province;
    }
};