[프로그래머스] 네트워크 (파이썬)

문제링크

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

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

문제풀이

이 문제는 dfs 를 사용해서 연결된 네트워크 set 의 개수가 몇개인지 구하는 문제이다.

문제에서 네트워크의 연결 상태를 n * n 의 2차원 배열로 주었다.

하지만, 이러한 데이터 형태는 사용하기가 까다로워 먼저 데이터를 사용하기 편하게 파싱했다.

 

[

  [1],

  [0,2],

  [1]

]

 

위와 같은 형태로 파싱했으며, 이는 0 번째 노드는 1번째 노드와 연결되있고 1번째 노드는 0,2 번째 노드와 그리고 마지막으로 2번째 노드는 1번째 노드와 연결되있다는걸 의미한다.

 

for 문으로 0번째 노드부터 마지막 노드까지 돌며 dfs() 를 진행하며, dfs() 가 진행되는 경우 count += 1 을 해준다.

위의 예시에서 예를들어 

for 문으로 0 번째 노드가 처음 dfs() 에 들어가면 count 는 1이 된다. 그 후  0 노드가 방문처리 되고, 0 과 연결되어 있는 1 노드 그리고 1과 연결되어 있는 2 노드 또한 모두 방문처리 된다.

남은 1, 2 번째 for 문에서는 이미 1,2 가 방문처리 되었기 때문에 dfs() 에 들어가지 않는다.

 

소스코드

def solution(n, computers):
    answer = 0;
    visited = [0] * n;
    link = [ [] for _ in range(n) ];
    
    for i in range(n):
        for index,c in enumerate(computers[i]):
            if (c == 1 and index != i):
                link[i].append(index);
    
    
    def dfs(number, visited):
        visited[number] = 1;
        for c in link[number]:
            if (not visited[c]):
                dfs(c, visited);
    cnt = 0;
    for i in range(n):
        if not visited[i]:
            dfs(i, visited);
            cnt += 1;
    
        
    
    return cnt;