[Algorithm] Programmers : 네트워크 by Python

[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/43162

📌문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명
예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

---

💡 문제 풀이

노드간 연결을 확인하는 문제로 보통 DFS/BFS로 해결할 수 있다.

모든 노드를 탐색하면서 몇 개의 그룹(서로 연결되어있거나 독립노드)으로 나눌 수 있는지 알아내면 된다.

• answer : 네트워크 수
• dx, dy : 행, 열의 4가지 방향(상, 하, 좌, 우)
• visited : 방문한 (행, 열) 좌표를 담는 리스트
• queue : BFS(deque 사용) - 연결된 노드를 담는다.
• stack : DFS(list 사용) - 연결된 노드를 담는다.

BFS(너비 우선 탐색) : 큐(queue)를 사용한 방법 - FIFO

파이썬 리스트(list)자료구조를 사용하여 가장 왼쪽의 값을 pop하면 리스트 내부의 값 재배치로 인한 시간복잡도가 증가하므로 deque를 즐겨 사용한다.

from collections import deque

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def solution(n, computers):
    answer = 0
    queue = deque([])
    visited = []
    for r in range(n):
        for c in range(n):
            if c in visited: break
            if computers[r][c] and (r, c) not in visited:
                answer += 1
                visited.append((r, c))
                queue.append(c)
                while len(queue):
                    nr = queue.popleft()
                    for c in range(n):
                        if computers[nr][c] and (nr, c) not in visited:
                            visited.append((nr, c))
                            queue.append(c)
    return answer

DFS(깊이 우선 탐색) : 스택(stack)을 사용한 방법 - LIFO

사용한 자료구조와 값을 빼내는 위치(LIFO vs FIFO)만 다를뿐 코드가 매우 유사하다.
※ 하지만, 문제의 유형(깊이 우선 vs 너비 우선)에 따라 시간차이가 날 수 있다.

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def solution(n, computers):
    answer = 0
    stack = []
    visited = []
    for r in range(n):
        for c in range(n):
            if c in visited: break
            if computers[r][c] and (r, c) not in visited:
                answer += 1
                visited.append((r, c))
                stack.append(c)
                while len(stack):
                    nr = stack.pop()
                    for c in range(n):
                        if computers[nr][c] and (nr, c) not in visited:
                            visited.append((nr, c))
                            stack.append(c)
    return answer

DFS, BFS를 복습할 수 있었던 문제😊