[프로그래머스-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입니다.

입출력 예

 

---

 

해결 아이디어

n개의 컴퓨터(정점), 연결 정보(computers)이 주어졌고 서로 이어진 컴퓨터 묶음의 개수를 구하는 문제이다.

따라서 우리는 하나의 정점에서 시작해 그 정점이랑 이어져있는 정점들을 탐색하며 하나로 묶음으로 간주하기 때문에, BFS/DFS를 사용하는 문제라는 생각을 할 수 있다.

나의 경우는, 이 탐색 알고리즘까지는 생각을 하였지만 answer을 어떤 경우에 업데이트 해야되는지가 헷갈렸다. 탐색을 모두 완료한 후에 각각 정점의 방문 여부를 나타내는 visited배열에서 visited[v]가 False라면, 이 정점을 방문하지 않았다라는 것으로 이전에 이것과 연결된 정점이 없었다는 것이다. 방문하지 않은 정점에서 탐색(DFS/BFS)를 한 번 시작하면, 그 정점이 속한 '네트워크 전체' 를 방문처리한다. 즉, 새로운 묶음이라는 것으로 이 경우에 answer을 1씩 더하면 된다.

따라서, 탐색을 시작한 횟수 = 네트워크 개수(answer)이다.

이 문제의 경우 DFS와 BFS풀이가 모두 가능하므로, 두 풀이로 모두 풀어보았다.

 

---

소스코드<Python>

1.재귀를 이용한 DFS 풀이

내가 처음에 접근했던 방식이다. 이전에 이론을 배울 때 DFS구현을 재귀로 하는 것을 먼저 배웠던 기억이 있어서, 우선 stack을 생각하지 못하고 재귀로 풀어보았다...

인접 리스트를 따로 만드는 것이 조금 번거롭다.

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

    #인접 리스트 생성
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                graph[i].append(j)
    
    def dfs(v, graph, visited):
        visited[v] = True
        for k in graph[v]:
            if not visited[k]:
                dfs(k, graph, visited)


    visited = [False] * n

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

    return answer

 

dfs 파이썬 소스코드에 따라 인접행렬을 따로 구해서 만들었지만, 인접 행렬을 구하지 않고 computers를 활용해 만들 수도 있다.

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

    def dfs(v):
        visited[v] = True
        for u in range(n):
            if computers[v][u] == 1 and not visited[u]:
                dfs(u)

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

computers[v][u] == 1이라는 것은 인접하다는 것으로, 굳이 인접행렬을 만들 필요가 없다. 코드가 훨씬 간단해졌다.

 

 

 

2. 스택을 이용한 DFS 풀이

DFS는 스택으로 풀 수 있다. pop()을 이용해 가장 최근에 넣은 정점부터 처리하는데, 이것은 DFS의 특성이다. 인접행렬을 구하기 위해 u= 0... n-1을 전부 훑으며 연결 여부를 확인한다.

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

    def dfs_stack(start):
        stack = [start]
        while stack:
            v = stack.pop()
            if visited[v]:
                continue
            visited[v] = 1
            for u in range(n):
                if computers[v][u] == 1 and not visited[u]:
                    stack.append(u)

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

 

 

3. BFS 풀이 - 큐를 이용

BFS는 스택대신 큐를 이용하여 시작 정점에서 가까운 정점부터 탐색하며, 큐에 넣을 때 방문 처리하여 중복 삽입을 막는다.

from collections import deque

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

    def bfs(start):
        q = deque([start])
        visited[start] = True                 # 큐에 넣는 순간 방문 표시
        while q:
            v = q.popleft()
            for u in range(n):
                if computers[v][u] == 1 and not visited[u]:
                    visited[u] = True         # 중복 삽입 방지
                    q.append(u)

    for i in range(n):
        if not visited[i]:                    # 새로운 네트워크 시작점
            bfs(i)
            answer += 1

    return answer

 

 

---

소스코드 <JavaScript>

1. DFS 풀이

function solution(n,computers){
    let answer = 0
    const visited = new Array(n).fill(false);

    const dfs = (start) => {
        const stack = [start];

        while(stack.length){
            const v = stack.pop();

            if(visited[v] === true){
                continue;
            }
            visited[v] = true;
            for (let u = 0; u <n; u++){
                if (computers[v][u] === 1 && !visited[u]) stack.push(u);
            }
        }
    }

    for(let i = 0; i<n; i++){
        if(!visited[i]){
            dfs(i);
            answer++;
        }
    }
    return answer;
}

 

2. BFS풀이

function solution(n, computers){
    const visited = Array(n).fill(false);
    let answer = 0;

    const bfs = (start) => {
        const queue = [start];
        visited[start] = true;
        while(queue.length > 0){
            const v = queue.shift();
            
            for (let u = 0; u < n; u++){
                if (computers[u][v] === 1 && !visited[u]){
                    visited[u] = true;
                    queue.push(u);
                }
            }
        }
    }

    for (let i = 0; i < n; i++){
        if (visited[i] === false){
            bfs(i);
            answer ++;
        }
    }
    return answer;
}