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

https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=swift

프로그래머스

 

접근

---

• 특정 노드에 대해 다른 노드들이 연결되어 있는지 모두 확인해야 하므로, 깊이 우선 탐색을 사용한다.

 

로직

---

• 노드 x에 대한 방문 여부를 저장하는 배열을 생성한다. 
• 네트워크는 여러 개 생성될 수 있다. 즉, 중간에 끊겨서 확인하지 못하는 노드가 발생될 수 있기 때문에 0부터 n-1 까지 반복문을 사용해 아직 점검하지 않은 노드가 있는지 확인한다.
• 위의 반복문 안에서 노드 K를 점검한다고 가정할 때, 아직 방문하지 않은 노드라면 깊이 우선 탐색을 진행하고, 새로운 네트워크를 탐색하는 것이므로 result 값을 1 증가시킨다. 
• 깊이 우선 탐색을 통해 방문하게 된 노드들은 모두 방문 표시를 한다. 
• result를 결과값으로 반환한다. 

 

코드

---

1. Swift 

func solution(_ n:Int, _ computers:[[Int]]) -> Int {

    var visit = [Bool](repeating: false, count: n)
    
    func network(_ k: Int) {
        for i in 0..<n{
            if computers[k][i] == 1 && !visit[i] {
                visit[i] = true
                network(i)
            }
        }
    }
    
    var result = 0
    for i in 0..<n{
        if !visit[i] {
            visit[i] = true
            result += 1
            network(i)
        }
    }
    
    return result
}

2. Python

def solution(n, computers):
    
    visit = [False] * n
    
    def network(k):
        for i in range(n):
            if computers[k][i] == True and visit[i] == False:
                visit[i] = True
                network(i)
    
    answer = 0
    for i in range(n):
        if visit[i] == False:
            visit[i] = True
            answer += 1
            network(i)
    
    return answer