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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

문제를 간단하게 설명하자면 다음과 같다.

노드의 갯수를 나타내는 n이 주어지고 해당 노드가 어느 노드와 이어져있는지를 알려주는 배열인 computers가 주어진다. 이 때, 연결되어서 이어지는 무리는 몇 개인지를 반환하는 것이다.

예를 들어, a,b,c 3개의 노드가 주어졌을 때, a-b, c라면 총 무리가 두 개가 발생하므로 2를 반환하는 것이다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. 순회 여부를 알기 위해 n크기 만큼 모두 false를 넣은 visited 배열을 만들어준다.

2. DFS 함수에서 index값을 순회했으므로 visited[index]=True로 대입한다.

3. DFS 함수의 for문에서 스스로의 연결은 의미가 없기 때문에 스스로의 값이 1일 때는 제외하고 나머지는 1일 때를 판단하여 연결이 된 노드를 찾는다.

4. 해당 노드가 순회하지 않은 노드라면 DFS함수를 재귀하여 또 어떤 노드와 연결이 되어있는지 계속 반복한다.

5. DFS 재귀함수가 종료되었다면 이는 연결된 무리를 모두 순회한 것이기 때문에 무리가 하나 있는 것으로 판단하고 answer++를 해준다.

 

필자가 작성한 코드는 다음과 같다.

def dfs(index, visited, computers,n):
    if index>n:
        return
    visited[index]=True #2번
    for j in range(len(computers)):
        if index!=j and computers[index][j]==1: #3번
            if visited[j]==False: #4번
                dfs(j, visited, computers,n)

def solution(n, computers):
    answer = 0
    visited=[False for _ in range(n)] #1번
    
    for i in range(len(computers)):
        if visited[i]==False:
            dfs(i, visited, computers,n) 
            answer+=1 #5번
    
    return answer