[LeetCode] 547. Number of Provinces

😎풀이

1. 각 출발지가 아직 방문되지 않은 노드라면, 지방 1 증가
2. 출발지로 도착 가능한 곳은 방문 처리
3. 깊이 우선 탐색을 통해 방문한 곳을 경유해 방문이 가능한 곳도 방문 처리
4. 지방의 수 반환

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length
    const visited = new Set<number>()
    let provinces = 0
    function dfs(from: number) {
        for(let to = 0; to < n; to++) {
            if(visited[to]) continue
            if(isConnected[from][to] === 0) continue
            visited[to] = true
            dfs(to)
        }
    }
    for(let i = 0; i < n; i++) {
        if(visited[i]) continue
        provinces++
        visited[i] = true
        dfs(i)
    }
    return provinces
};