[프로그래머스 - DFS/BFS] 네트워크 (Python3)

https://programmers.co.kr/learn/courses/30/lessons/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	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개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

 

 

 

 

풀이

==> 각 노드는 혼자든 여럿이든 하나의 네트워크에 속해 있고, DFS로 탐색하며 방문한 적이 없는 노드들을 방문해주면 된다. 말로 설명하기 너무 어려운 것 같다.

 

그림을 그려서 설명해보겠다.

0,1,2,3,4,5,6의 노드가 있다고 해보자

이런 형태의 네트워크 그림이 주어진다고 하면

결과적으로 0-1-4,  2-5-6,  3  이렇게 3가지 네트워크가 나오게 된다.

 

문제 풀이 과정

- 모든 노드들을 한번씩 dfs로 탐색해보는데 방문하지 않은 노드일 때만 dfs함수를 호출한다.

- dfs 함수에는 현재 노드를 인자로 넣어주고 함수가 호출되면 일단 현재 노드를 방문했다고 표시해준다.

- 현재 노드의 연결관계(computer[현재노드인덱스])를 살펴보고 자기자신이 아니면서 연결된 노드 중 방문하지 않은 노드가 있으면 그 노드로 dfs재귀함수를 호출한다.

- 모든 연결관계를 살펴봤다면 하나의 네트워크를 탐색한 것이므로 1을 리턴해준다.

 

 

작성 코드

def solution(n, computers):
    answer = 0
    
    visited = [0 for i in range(n)]
    for i in range(n):
        if visited[i] == 0:
            answer += dfs(n, computers, i, visited)
    return answer

def dfs(n, computers, node, visited):
    visited[node] = 1
    for i in range(n):  # 자기자신이 아니면서 (연결된 && 방문하지 않은) 노드 있으면 재귀호출
        if i != node and computers[node][i] == 1 and visited[i] == 0:
            dfs(n, computers, i, visited)
    return 1    # 한 네트워크 방문 다 끝나면 1 리턴