📚

LeetCode 547. Number of Provinces - 配列の要素ごとの深さ優先探索処理

に公開
LeetCode
tech

547. Number of Provinces

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

  • 複数の都市があり、接続されている都市と接続されていない都市がある
  • 州は接続された都市のグループである
  • 州の合計数を返す

Approach①

ruby

  • 各nodeのループの中で深さ優先探索をして、事前にvisitフラグを立てて接続された都市のグループを調査する
def find_circle_num(is_connected)
    number_of_components = 0
    visit = Array.new(is_connected.length, false)

    is_connected.length.times.each do |i|
      if !visit[i]
        number_of_components += 1
        dfs(i, is_connected, visit)
      end
    end
    
    return number_of_components 
end

# [[1,1,0],[1,1,0],[0,0,1]]
# [1,1,0]の単位で接続されたノードを深さ優先探索で探索する。最初のループでvisit[1]はtrueとなるため、接続済みのノードには訪問しない。
def dfs(node, is_connected, visit)
  visit[node] = true
  is_connected.length.times.each do |i|
    if is_connected[node][i] == 1 and !visit[i]
      dfs(i, is_connected, visit)
    end
  end
end

Approach②

  • 深さ優先探索のアプローチで、再帰ではなくスタックを利用した実装
def find_circle_num(is_connected)
    number_of_components = 0
    visit = Array.new(is_connected.length, false)

    is_connected.length.times.each do |i|
      if !visit[i]
        number_of_components += 1
        dfs_with_stacks(i, is_connected, visit)
      end
    end
    
    return number_of_components 
end

def dfs_with_stacks(node, is_connected, visit)
  stacks = [node]

  while ( n = stacks.pop )
    is_connected.length.times.each do |i|
      if is_connected[n][i] == 1 and !visit[i]
        visit[i] = true
        stacks.push(i)
      end
    end
  end
end

python

  • 深さ優先探索でスタックを使ったアプローチ
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        numberOfComponents = 0
        visited = [False] * len(isConnected)
        
        for i in range(len(isConnected)):
          if not visited[i]:
            numberOfComponents +=1
            
            stacks = [i]
            while stacks:
              node = stacks.pop()
              for j in range(len(isConnected)):
                if isConnected[node][j] and not visited[j]:
                  visited[j] = True
                  stacks.append(j)
        
        return numberOfComponents

typescript

function findCircleNum(isConnected: number[][]): number {
    let visited: boolean[] = new Array(isConnected.length).fill(false)
    let stacks: number[]

    let numberOfComponents = 0
    for(let i = 0; i<isConnected.length; i++){
      if (!visited[i]){
        numberOfComponents += 1

        stacks = [i]
        while(stacks.length > 0){
          const node = stacks.pop()
          for(let j = 0; j<isConnected.length; j++){
            if(isConnected[node][j] && !visited[j]){
              visited[j] = true
              stacks.push(j)
            }
          }
        }

      }
    } 
    return numberOfComponents
};

golang

func findCircleNum(isConnected [][]int) int {
    var visited = make([]bool, len(isConnected))
    numberOfComponents := 0

    for i := 0; i<len(isConnected);i++{
      if !visited[i] {
        numberOfComponents++
        stacks := []int{i}

        for len(stacks)>0 {
          node := stacks[len(stacks)-1]
          stacks = stacks[:len(stacks)-1]
          // 処理順に影響がないためキューを使って実装することもできる。Golangにはスタックを扱うpop関数がないため、キュー実装の方が可読性は高いか。
          // node := stacks[0]
          // stacks = stacks[1:]

          for j := 0; j<len(isConnected);j++{
            if isConnected[node][j] == 1 && !visited[j] {
              visited[j] = true
              stacks = append(stacks, j)
            }

          }
        }
      }
    }
    return numberOfComponents
}

ポイント

  • 各都市の接続を木構造と捉えて深さ優先探索アプローチを行う。
    • どの都市がすでに探索されたか追跡するために、visited配列を用意する
    • ループの中で、まだ訪問していない都市iを見つけたら、それが新しい州（連結成分）の始まりとする

Discussion