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

Programmers 네트워크

풀이

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    def dfs(node):
        visited[node] = True
        
        for next_node in range(n):
            if computers[node][next_node] == 1 and not visited[next_node]:
                dfs(next_node)
    
    for i in range(n):
        if not visited[i]:
            dfs(i)
            answer += 1
    
    return answer

이해

0번 <-> 1번 <-> 2번에서 0번과 2번처럼 직접 연결되어 있지 않더라도, 1번을 통해 연결되어 있다면 같은 네트워크

DFS

Depth First Search의 약자, 깊이 우선 탐색

• 한 방향으로 갈 수 있는 곳까지 깊게 들어간 뒤, 더 이상 갈 곳이 없으면 다시 돌아와서 다른 경로를 탐색하는 방식

• 보통 재귀 함수나 스택을 이용해서 구현함

BFS

Breadth First Search의 약자, 너비 우선 탐색

• 현재 위치에서 가까운 노드부터 차례대로 방문하는 방식

• 한 곳을 깊게 들어가기보다는 현재 노드와 연결된 주변 노드들을 먼저 확인

• 보통 큐를 이용해서 구현함

→ 이 문제는 최단 거리를 구하는 것이 아니라, 연결된 컴퓨터 묶음의 개수를 구하는 것이기 때문에 DFS와 BFS 모두 사용할 수 있다.

기존에 나는 연결된 컴퓨터 번호를 arr 배열에 저장한 뒤, 방문하지 않은 컴퓨터 수를 이용해 네트워크 개수를 계산하려고 했다.

하지만 이 방식은 간접 연결을 제대로 처리하기 어려웠다.

단순히 연결된 숫자를 저장하는 방식이 아니라, 한 컴퓨터에서 시작해 연결된 모든 컴퓨터를 끝까지 탐색해야했다.

나의 풀이는 DFS를 활용하였다.

1. 모든 컴퓨터를 하나씩 확인

2. 아직 방문하지 않은 컴퓨터 찾기

3. 그 컴퓨터에서 DFS 또는 BFS 시작

4. 연결된 모든 컴퓨터를 방문 처리

5. 탐색이 끝나면 네트워크 1개를 찾은 것

6. answer를 1 증가시킴

BFS를 이용한 풀이 방식

from collections import deque

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

    for i in range(n):
        if not visited[i]:
            queue = deque([i])
            visited[i] = True

            while queue:
                node = queue.popleft()

                for next_node in range(n):
                    if computers[node][next_node] == 1 and not visited[next_node]:
                        visited[next_node] = True
                        queue.append(next_node)

            answer += 1

    return answer