#32 [파이썬] LeetCode: Number of Provinces

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

Number of Provinces - LeetCode

 

---

 

코드

from typing import List

class Solution:
    def dfs(self, i: int, isConnected: List[List[int]]):
        isConnected[i][i] = 0
        for j in range(len(isConnected)):
            if isConnected[i][j] == 1:
                isConnected[i][j] = 0
                isConnected[j][i] = 0
                self.dfs(j, isConnected)
        return
        
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        cnt = 0
        for i in range(len(isConnected)):
            if isConnected[i][i]:
                self.dfs(i, isConnected)
                cnt += 1
        return cnt

 

---

 

• number-of-islands 문제와 비슷하다. 연결된 노드들이 섬과 같다고 생각할 수 있다.
• isConnected[i][j]와 isConnected[j][i]가 같으므로 둘 중 한 군데만 방문해도 두 가지 모두 0으로 처리한다.
• 재귀말고 아래와 같이 스택으로도 풀 수 있다.

#스택 풀이

from collections import deque

class Solution(object):
    def findCircleNum(self, isConnected: List[List[int]]):
        result = 0
        n = len(isConnected)
        visit = [0 for _ in range(n)]
        
        for i in range(n):
            if visit[i]:
                continue
            que = deque()
            que.append(i)
            visit[i] = 1
            
            while len(que) > 0:
                idx = que.popleft()
                for j in range(n):
                    if visit[j]==0 and isConnected[idx][j]==1:
                        que.append(j)
                        visit[j] = 1
            
            result += 1
        
        return result