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

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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개의 네트워크가 있습니다.

---

나의 풀이

BFS / DFS의 가장 기본적인 형태인데 왜 3단계인지 모르겠다.

나는 BFS로 풀이했다.

2021.05.23 - 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

2021.06.26 - 깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

 

from collections import deque

def bfs(computers, start, visited):
    if visited[start]: return 0
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for i in computers[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    return 1

def solution(n ,computers):
    computers = [[i for i in range(n) if computers[row][i]==1] for row in range(n)]
    visited = [False] * n
    answer = 0
    for i in range(n):
        answer += bfs(computers, i, visited)
    return answer

주어진 computer를 약간 가공해야한다.

<인접 행렬>과 <인접 리스트>

주어진 그래프가 위와 같을 때 그래프를 표현할 수 있는 방법은 크게 <인접 행렬>과 <인접 리스트>로 나뉜다.

<인접 행렬>의 경우 각 노드가 연결되어 있다면 1로 표시된다. 그래서 특정 노드들이 연결되어 있는지 확인할 때는 인접 행렬이 훨씬 빠르다. 하지만 노드가 많고, 연결된 간선이 적을 때는 많은 메모리를 낭비하게 된다. 또한 위 그래프처럼 방향이 없는 간선일 때는 형광펜으로 그은 대각선을 기준으로 양쪽이 대칭을 이룬다. (대각선도 모두 1 혹은 0이다)

<인접 리스트>의 경우 각 노드에 연결된 노드들의 정보를 가지고 있다. 그래서 특정 노드들이 연결되어 있는지 확인하기 위해서는 특정 노드에 저장된 정보를 쭉 확인하면서 발견해야 하기 때문에 탐색 속도가 느리다. 반면, 메모리의 낭비는 최소화 할 수 있다. 이 문제처럼 특정 노드에 연결된 모든 노드들을 탐색하는 경우에는 <인접 리스트> 방식이 더 효율적이라고 생각한다.

문제에서 주어지는 computers는 <인접행렬>의 형태로 주어진 것이다.

하지만 BFS를 사용할 때는 인접 리스트를 사용하는 것이 더 편리하다. 그렇기에 주어진 computers를 <인접 리스트> 형태로 바꿔주는 작업이 필요하다.

computers = [[i for i in range(n) if computers[row][i]==1] for row in range(n)]

위 코드 한줄로 간편히 변경 가능하다.

아이디어

네트워크의 개수를 파악하는 방법은 간단하다.

BFS() 함수를 돌게 되면 만약 0번 컴퓨터부터 시작하면 0번 컴퓨터와 연결된 모든 컴퓨터를 방문하게 된다. visited에 방문 표시를 하면 된다.

이렇게 모든 컴퓨터(노드)를 순회하며 만약 방문하지 않았던 컴퓨터가 발견되면 앞서 탐색한 컴퓨터와 연결되지 않았던 것이므로 answer을 1 증가시킨다.

마지막까지 탐색 후 answer에 저장된 값이 네트워크의 개수가 된다.