[LeetCode] 547. Number of Provinces

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

Number of Provinces - LeetCode

문제 유형 : 완전 탐색 / dfs

문제 난이도 : Medium

 

문제

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

 

n개의 도시가 있다. isConnected에 연결 정보가 저장되어 있다. 0은 연결되어있지 않음을 의미하고, 1은 연결되어있음을 의미한다.

몇 개의 지방으로 나눠지는지 구하여라.

 

풀이

dfs를 이용하여 연결된 모든 노드를 방문한다.

그 뒤, provinces의 수를 하나 키운다. 이미 방문한 노드이면 건너뛰면 된다.

이 과정을 n번 반복해주면 된다.

 

코드(C++)

class Solution {
public:
    void dfs(int city, vector<bool>& visited, vector<vector<int>>& isConnected) {
        visited[city] = true;
        for (int neighbor = 0; neighbor < isConnected.size(); ++neighbor) {
            if (isConnected[city][neighbor] == 1 && !visited[neighbor]) {
                dfs(neighbor, visited, isConnected);
            }
        }
    }
    
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int provinces = 0;



        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                provinces++;
                dfs(i, visited, isConnected);
            }
        }

        return provinces;
    }
};