[프로그래머스] 네트워크(python)

문제 링크 - https://programmers.co.kr/learn/courses/30/lessons/43162

나의 풀이(bfs)

from collections import deque
# cnt = 0
def solution(n, computers):
    visited = [False] * n
    cnt = 0
    
    def bfs(start): 
        queue = deque()
        queue.append(start)
        visited[start] = True
        nonlocal cnt
        # global cnt
        
        while queue:
            v = queue.popleft()
            for i in range(len(computers[v])):
                if not visited[i] and computers[v][i] ==1:
                    visited[i] = True
                    queue.append(i)
                    cnt+=1
            
    for i in range(n):
        bfs(i)
        
    return n-cnt

• 백준의 연결요소의 개수 문제와 상당히 비슷했다.
• 만약 방문하지 않았고 연결되어 있다면 연결 갯수(cnt) +1
• 컴퓨터 갯수에서 연결된 수를 빼주면 답
• 만약 solution 함수 안에서 cnt를 선언하고 bfs 함수 내에서 cnt를 사용하려면 nonlocal
• cnt를 solution 함수 밖 전역에서 선언하고 bfs 함수 내에서 cnt를 사용하려면 global

다른 사람의 풀이(dfs)

def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)]
    def dfs(computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            # for i in range(len(computers)-1, -1, -1):
            for i in range(0, len(computers)):
                if computers[j][i] ==1 and visited[i] == 0:
                    stack.append(i)
    i=0
    while 0 in visited:
        if visited[i] ==0:
            dfs(computers, visited, i)
            answer +=1
        i+=1
    return answer

느낀점

• nonlocal, global 확실하게 알기
• bfs로만 풀지말고 dfs로도 풀어보기!!!!