[프로그래머스] 네트워크_python

📘 level3 네트워크 (DFS/BFS)

✅ 문제

https://programmers.co.kr/learn/courses/30/lessons/43162

✅ 풀이 방식

1. i 노드(의 연결) 탐색 시작 : dfs(i)
2. i 노드와 연결된 다른 노드가 있는지 확인 : computers[i][j]
   • 연결되었있다면 해당 노드(j) 탐색 시작 : dfs(j)
3. 더 이상 연결된 노드가 존재하지 않으면 네트워크 수(result) 값 +1 : result += 1

✅ 코드

def solution(n, computers):
    def dfs(i):
        chk[i] = True  # 방문 처리
        for j in range(n):  # 다른 노드들과의 연결보기위해 노드 수(n)만큼(나 자신 포함) (행)
            if computers[i][j] and not chk[j]:
                #!(computers[i][j]) : 값이 1 -> j노드와 연결되어 있다
                #!(chk[j]) : true -> 방문한 적이 없다
                dfs(j)

    result = 0  # 네트워크 수 (정답)
    chk = [False] * n  # 해당 노드 방문 체크

    for i in range(n):  # 노드 수(n)만큼 방문 (열)
        if not chk[i]:  # (chk[i]가 false) -> 방문한 적 없는 노드인 경우
            dfs(i)
            result += 1

    return result

✅ 참고

https://codinglevelup.tistory.com/175