[프로그래머스] "네트워크" (+파이썬 코드)

Question. 프로그래머스 깊이/너비 우선 탐색(DFS/BFS) > 네트워크

 

 

 

---

Answer.

 

computers라는 인접행렬(adjacency matrix) graph가 주어지는데, 

해당 graph에서 connected component가 몇 개인지 구하는 문제이다.

 

bfs로 풀 수도 있고, dfs로 풀 수도 있다.

 

주어진 인접행렬을 이용해 DFS로 풀면 다음과 같다.

 

sol1) 인접행렬 + dfs

 

1) i번째 노드를 방문하지 않았다면, 스택에 i번째 노드를 넣는다.

2) stack의 요소를 하나씩 pop 하며 visited 배열에 해당 노드를 true 처리한다.

3) 해당 노드와 연결된 노드들 중 방문하지 않은 노드들을 스택에 넣어준다.

---> dfs 함수 부분

 

4) 1~3을 n개의 노드에 대해 반복한다. 

---> for문 부분

 

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

    def dfs(n, computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            for i in range(n):
                if computers[j][i] == 1 and visited[i] == 0:
                    stack.append(i)

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

 

한편, 인접행렬을 인접리스트로 바꾸고 bfs로 구현하면 다음과 같다. (물론 dfs를 써도 상관없다)

 

sol2) 인접리스트로 바꾸기 + bfs

 

1) 인접행렬을 인접리스트로 바꾼다.

---> array_to_graph 함수 부분

 

2) i번째 노드를 방문하지 않았다면, queue에 i번째 노드를 넣는다.

3) queue의 요소를 하나씩 pop 하며 visited 배열에 해당 노드를 true 처리한다.

4) 해당 노드와 연결된 노드들 중 방문하지 않은 노드들을 queue에 넣어준다.

---> bfs 함수 부분

 

5) 2~4를 n개의 노드에 대해 반복한다. 

---> for문 부분

from collections import defaultdict
from collections import deque

def array_to_graph(computers, n):
    graph = defaultdict(list)
    for i in range(n):
        for j in range(n):
            if i != j and computers[i][j]:
                graph[i + 1].append(j + 1)
    return graph

def solution(n, computers):
    answer = 0
    graph = array_to_graph(computers, n)
    visited = [False] * (n + 1)

    def bfs(graph, start, visited):
        q = deque([start])
        while q:
            pos = q.popleft()
            if visited[pos]:
                continue
            visited[pos] = True
            for nextnode in graph[pos]:
                q.append(nextnode)

    for i in range(1, n + 1):
        if not visited[i]:
            bfs(graph, i, visited)
            answer += 1

    return answer

 

sol 1) 인접행렬 + dfs/bfs
Time Complexity	\[O(N^{2})\]
Space Complexity	\[O(N)\]
sol 2) 인접리스트로 바꾸기 + dfs/bfs
Time Complexity	\[O(N^{2})\]
Space Complexity	\[O(N+E)\]

*space complexity 계산시, 처음에 주어지는 parameter를 위한 space는 제외