[프로그래머스]네트워크-DFS/BFS

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

DFS 알고리즘 이용

def solution(n, computers):
    visited = [0 for _ in range(n)]
    cnt = 0

    def dfs(visited, i):
        visited[i] = True
        
        for j in range(n):
            # 컴퓨터가 연결되어 있고, 방문하지 않은 곳이라면 방문
            if computers[i][j] == 1 and not visited[j]:
                dfs(visited, j)
        
    # 방문을 모두 할 때까지 반복
    while False in visited:
        for i in range(n):
            if not visited[i]:
                # dfs 안에서 이어진 모든 컴퓨터를 방문하게 된다.
                # 즉, 이 과정이 1개의 네트워크를 의미한다.
                dfs(visited, i)
                cnt += 1

    return cnt

 

코드 설명

1. 기본적으로 모든 컴퓨터를 방문할 때 까지 반복합니다.
   1. 만약 방문하지 않은 컴퓨터라면 dfs 함수를 호출합니다.
   2. 이 일련의 과정이 1개의 네트워크를 찾는 것을 의미합니다.
2. dfs 함수에서는 연결되어 있는 컴퓨터의 끝까지 방문합니다. (방문한곳은 제외)

즉, 예시1번의 경우 컴퓨터1 -> 컴퓨터2를 방문하고 이를 1개의 네트워크로 간주.

3번 컴퓨터를 방문하고 이를 1개의 네트워크로 간주. 총 2개의 네트워크가 구해집니다.

 

Point : computer[i][j] = 1 이라면 연결되어 있는 컴퓨터를 뜻합니다.

해당 문제에서 dfs를 이용하는 방식은 dfs의 특징을 이용하여 하나의 컴퓨터에서 연결된 마지막 컴퓨터까지 방문하고 이를 1개의 네트워크로 간주하는 것 입니다.

 

BFS 알고리즘 이용

from collections import deque


def solution(n, computers):
    queue = deque()
    visited = [False for _ in range(n)]    
    
    def bfs():
        cnt = 0
        
        # 모든 컴퓨터를 방문할 때까지 반복
        while False in visited:
            # 방문안한 컴퓨터 중 가장 최소의 index
            i = visited.index(False)
            queue.append(i)
            
            # ===== 1개의 네트워크를 찾는 cycle =====
            while queue:
                i = queue.popleft()
                visited[i] = True
                for j in range(n):
                    # 이어진 모든 컴퓨터에서 방문 안한 곳을 큐에 추가한다.
                    if computers[i][j] == 1 and not visited[j]:
                        queue.append(j)
            cnt += 1
            # ===== 1개의 네트워크 탐색 완료 =====
            
        return cnt
    
    return bfs()

 

코드 설명

1. DFS와 마찬가지로 모든 컴퓨터를 방문할 때까지 반복합니다.
2. 방문하지 않은 컴퓨터 중의 가장 최소의 인덱스(컴퓨터)를 구해 큐에 넣습니다.
3. 큐가 있는 동안 반복을 수행합니다.
   1. 큐에서 popleft()하여 방문처리를 수행합니다.
   2. 이어진 모든 컴퓨터에서 방문하지 않은 곳을 큐에 추가합니다.
4. 1개의 네트워크 탐색을 완료했으니 cnt를 +1 합니다.

 

Point : computer[i][j] = 1 이라면 연결되어 있는 컴퓨터를 뜻합니다.

대부분의 방식은 전형적인 bfs와 같습니다. 다만 해당 문제를 구현할 때 .index()라는 파이썬의 함수를 통해서 가장 최소의 index를 구하는 기법이 사용되었습니다.