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

<문제 설명>

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

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

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미한다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있다.

 

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하면되는 문제이다.

 

입출력의 예는 다음과 같다.

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

 

<문제 풀이 아이디어>

i번째 노드를 방문하지 않았다면, 스택에 i번째 노드를 넣는다.
stack의 요소를 하나씩 pop해서 visited 배열에 해당 노드를 true 처리한다.
해당 노드와 연결된 노드들 중 방문하지 않은 노드들을 스택에 넣어준다.
위 3가지를 n개의 노드에 대해 반복한다.

 

<문제 풀이 코드>

def solution(n, computers):
    #인접행렬 + dfs
    answer = 0
    visited = [0]*n; #n개의 0값을 가지는 리스트 만들기

    def dfs(n,computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0: #방문하지 않았다면
                visited[j] = 1 #방문 체크
            for i in range(n):
                if computers[j][i] == 1 and visited[i] == 0:
                    #해당 노드와 연결되어있고, 방문하지 않은 노드를 stack에 추가
                    stack.append(i)
    for i in range(n):
        if not visited[i]:
            dfs(n, computers, visited, i)
            answer += 1
    return answer

채점결과