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

프로그래머스 네트워크

문제설명

---

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

 

 

1-2로 이루어진 네트워크 하나와 3 단일로 구성된 네트워크로 총 2개의 네트워크가 존재	1-2-3으로 구성된 총 1개의 네트워크가 존재

 

문제해설

---

해당 문제는 간단하게 그저 연결되어 있는 노드의 덩어리 개수를 의미한다.

주로 그래프 탐색 문제 유형을 처음 접할 때 만날 수 있는 문제이다.

 

대부분의 문제에서는 영역의 개수로 나타나는 이 문제는 DFS를 통해 해결할 수 있다.

파이썬으로 해결한다면 더욱 쉽게 할 수 있다.

 

입력은 n과 computers로 들어온다.

 

computers에는 각 인접리스트가 들어 있어서, 노드들의 연결관계를 파악할 수 있다.

본 문제는 나름 간단하게 해결할 수 있었고, 문제는 아래와 같은 순서로 풀었다.

 

가장 먼저 visited 리스트를 만들어서, 지금까지 지나온 경로에 다시 들어가지 않도록 구별한다.

그 이후로는 visited 리스트를 순회하면서 방문하지 않은 노드에 대해서 stack에 넣고 인접리스트를 순회한다.

이어서 방문한 노드에는 visited로 확인하고, 방문하지 않은 노드가 있으면 해당 노드들을 모두 순회하며 visited를 업데이트 한다.

 

그렇게 stack에 들어간 정보가 없으면, 하나의 네트워크를 모두 탐색했다고 판단, answer에 1을 더했다.

 

이렇게 visited 리스트를 모두 순회하면 결과값인 answer를 return한다.

해결코드

---

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

    stack.append(0)

    for i, v in enumerate(visited):
        if v == 1:
            continue
        else:
            stack.append(i)
        
        while stack:
            cur = stack.pop() 
            visited[cur] = 1

            for i, next in enumerate(computers[cur]):
                if next == 0 or visited[i] == 1 or i == cur:
                    continue
                else:
                    stack.append(i)
        answer += 1
                
    return answer

 

해당 문제는 DFS 개념이 있다면 쉽게 해결할 수 있는 문제였다.