[코딩 테스트] 프로그래머스 - 네트워크 (Lv.3) in Python

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

연결되었으면 1, 아니면 0.

 

예시:

n = 3

computers = [[1,1,0], [1,1,0], [0,0,1]]

 

return // 2

 

- 처음에 문제 해석에 좀 걸렸다... 대체 저 배열이 뭘 의미하는거야? ㅠ 하고..

- computers 배열 안 배열은, 각 인덱스 넘버에 해당하는 컴퓨터의 connectivity를 의미한다.

ex. 0번 컴퓨터 -> [1,1,0].

    (0번 - 0번)은 연결 (자기 자신)

    (0번 - 1번)은 연결

    (0번 - 2번)은 비연결

-

 

- 따라서 (1-2)가 연결되어 있는 네트워크 하나, (3) 단독으로 있는 네트워크 둘,

  해서 총 2개의 네트워크가 있고 답은 2다.

 

풀이

- 처음 노드에서 시작해서 연결된 그래프의 끝까지 탐색한다. 더 이상 연결된 노드가 없으면 탐색 끝, 네트워크 숫자를 하나 늘린다.

    - 탐색하면서 거쳐간 노드는 visited에 표시를 해줌.

- visited 안 된 노드가 있다면, 거기서 시작해서 다시 탐색 시작

 

- 깊이 우선 탐색 (DFS)와 너비 우선 탐색 (BFS)모두 가능하다.

- 외부 라이브러리 (deque)를 import하는 수고를 덜기 위해, 깊이 우선 탐색 (기본 배열 구조로 스택 구현 가능함)을 선택했다.

- 리마인더: DFS - 스택, BFS - 큐 이용!

 

코드 구현

def solution(n, computers):
    count = 0
    visited = [0] * n
    stk = [0]
    
    while True:
        while len(stk) > 0:
            curr = stk.pop()
            visited[curr] = 1
            for i, conn in enumerate(computers[curr]):
                if conn == 1 and visited[i] == 0:
                    visited[i] = 1
                    stk.append(i)
        count += 1
        if 0 in visited:
            curr = visited.index(0)
            stk.append(curr)
        else:
            break
            
    return count