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

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

프로그래머스

 

 

문제설명

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

 

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

 

문제 해결 방법

 

 

이런 문제는 최적의 해 보다는 모든 요소를 탐색하는 것이 목적이다.

모든 요소를 탐색하기 위해 DFS가 좋다. 

 

computers를 그래프로 표현한 후, 방문 테이블을 만들고, 방문 테이블을 통해 그래프를 DFS로 몇번 탐색 했는지를 출력하면 된다. 

 

 

 

이 문제를 bfs로 풀려고 했던 과거의 내자신 ㅠㅠ 

 

 

 

코드 구현

 

주석 없는 버전

 

def dfs(computers, visited, node):
        visited[node] = True
        for idx, connected in enumerate(computers[node]):
            if connected and not visited[idx]:
                dfs(computers, visited, idx)

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

 

 

 

 

 

 

def dfs(computers, visited, node):
    # 조회를 하면 해당 노드에 대해 방문처리를 해준다. 
    # 해당 노드를 통해 computers에 딸린 다른 노드들을 반복문을 통해 조회하고,
        # 연결 여부와 방문 여부를 확인한다. 
    # 연결된 것을 통해 깊이 우선 탐색을 계속 해나간다. 
    visited[node] = True
    for index, connected in enumerate(computers[node]):
        if connected and visited[index] == False:
            dfs(computers, visited, index)
    
def solution(n, computers):
    answer = 0
    # 방문여부를 담는 크기 n만큼의 배열 
    
    visited = [False] * n
    
    for i in range(n):
        if visited[i] == False:
            dfs(computers, visited, i)
            answer+=1
    # 반복문을 통해 노드를 0~n까지 순회하며 깊이 우선 탐색을 한다. 
        # 깊이 우선 탐색 dfs에는 computers라는 그래프와, visited, 그리고 노드를 보내준다. 
    # 깊이 우선 탐색이 끝나면 answer +1 을 해준다. 
    return answer

 

 

시간/공간 복잡도

 

O(N^2)

 

 

최적화 및 개선

 

따로 하지 않음.

어려웠던 점

 

아직 DFS, BFS사용에 서툰것 같다.