Daily LeetCode Challenge - 547. Number of Provinces

Problem From.

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

오늘 문제는 isConnected 배열에 각각의 노드가 연결되어있는지 안되어있는지 정보를 통해서, 연결되어있지 않고 떨어져있는 노드의 모음이 총 몇개인지 구하는 문제였다.

이 문제는 DFS 를 통해서 풀 수 있었는데, 먼저 방문하지 않은 노드를 통해 탐색하면서, 해당 되는 노드를 모두 방문한 것으로 만든다. 일련의 과정이 끝나면 정답에 1 을 더해주고, 위의 과정을 반복하면 떨어져있는 노드의 모음을 구할 수 있었다.

class Solution {
    fun findCircleNum(isConnected: Array<IntArray>): Int {
        val visited = mutableSetOf<Int>()

        fun dfs(from: Int) {
            for(i in isConnected.indices) {
                if (isConnected[from][i] == 1 && visited.add(i)) {
                    dfs(i)
                }
            }
        }

        var answer = 0
        for (i in isConnected.indices) {
            if (visited.add(i)) {
                dfs(i)
                answer += 1
            }
        }
        
        return answer
    }
}