[프로그래머스] 네트워크 파이썬

프로그래머스 - 네트워크

문제

• 주어진 2차원 행렬에서 서로 연결된 네트워크가 총 몇가지가 있는지를 리턴하는 문제
• 주어진 행렬로 그림을 그려보면 문제의 예시가 쉽게 이해된다.
• 먼저 각 컴퓨터는 네트워크에 연결되어 있기 때문에 (0, 0), (1, 1), (2, 2)와 같이 본인 자신은 연결되어 있어 1로 표기된다.
• 그 외에는 행에서 열로 연결된다라는 가정하에 그림을 그려보면 된다. 예를 들어 0행의 1열이 1이라면 0번 컴퓨터와 1번 컴퓨터가 연결되어있다라는 뜻이 된다.

코드

def dfs(com, computers, visited):
    visited[com] = True

    for idx, value in enumerate(computers[com]):
        if value and not visited[idx]:
            dfs(idx, computers, visited)


def solution(n, computers):
    visited = [False] * n
    cnt = 0

    for i in range(n):
        if not visited[i]:
            dfs(i, computers, visited)
            cnt += 1

    return cnt

설명

• 네트워크가 구분되는 경우의 수를 구하기 위해서 DFS로 풀기로 결정했다.
• DFS의 종료 조건을 결정해야하는데, 이 문제같은 경우에는 연결되는 네트워크의 탐색이 모두 종료됐을 경우에 하나의 네트워크로 연결되었다고 판단하고 DFS 종료 조건을 설정한다. 즉, dfs 함수를 한번 실행하고 해당 함수가 모두 종료되면 cnt를 1 증가시켜준다. 이는 0번 컴퓨터와 연결된 네트워크의 탐색을 모두 마친 후 카운트를 증가시킨다는 의미이다.
• dfs함수가 실행됐다는 것은 방문하지 않은 컴퓨터의 탐색을 실행한 것이므로 방문을 체크해주는 visited 값을 True로 변경해준다.
• 이후 2차원 행렬을 풀어내기 위해서 해당 컴퓨터와 연결된 컴퓨터의 현황을 알 수 있는 반복문을 통해 재귀를 실행시켜주면 된다.

부족했던 점

• 단순히 이 전의 DFS 문제처럼 상태 트리의 level이 하나씩 증가하고 이 값이 어떤 주어진 수 n에 왔을 때 DFS의 종료조건이 성립하는 방식이 아니라서 종료조건을 어떻게 설정해야할지에서 헷갈렸다.