프로그래머스: 네트워크 (파이썬, DFS)

비교적 쉬운 난이도의 문제였다. DFS를 통해 그래프를 탐색하는 전형적인 문제였기 때문이다. LV3에서 정답률이 높은 문제가 LV2에서 정답률이 낮은 문제보다 쉬운 것 같다..

먼저 두 노드간에 간선 유무를 2차원 배열을 통해서 알려주는데 인접 행렬을 이용해서 그래프를 표현한다. 그래프를 표현하는데는 인접 리스트와 인접 행렬이 있는데 난 인접 행렬을 선호하고 그 중에서도 본 문제풀이와 같이 부모, 자식을 각각의 인덱스에 해당하는 리스트에 넣어서 구현하는 방법을 선호한다.

 

문제풀이 코드는 다음과 같다.

def dfs(node, graph, visited):
    visited[node] = True
    for child in graph[node]:
        if not visited[child]:
            dfs(child, graph, visited)


def solution(n, computers):
    answer = 0
    graph = [[] for _ in range(n)]
    # 인접 행렬 구현
    for i in range(len(computers)):
        for j in range(len(computers[0])):
            if computers[i][j] == 1:
                if i not in graph[j]:
                    graph[j].append(i)
                if j not in graph[i]:
                    graph[i].append(j)
    # 방문 여부 배열
    visited = [False for __ in range(n)]
    for k in range(n):
        if not visited[k]:
            dfs(k, graph, visited)
            answer += 1
    return answer

인접행렬에서 DFS로 탐색을 하면 연결되어 있는 노드들은 모두 방문하게 된다.

Boolean 배열을 통하여 한번 방문한 곳은 다시 방문하지 않게 하고 DFS로 탐색을 할때마다 네트워크 하나를 탐색하는 것이므로 정답에 1을 더해주면 된다.