[Programmers] 네트워크 (Swift)

문제 : 

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

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

 

1. 문제 이해하기

• 노드와 간선으로 이어져 있는 트리(네트워크)의 개수를 리턴하는 문제
• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수
• 각 컴퓨터는 0부터 n-1인 정수로 표현
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현
• computer[i][i]는 항상 1

 

2. 문제 풀이 생각하기

1. 처음에는 백준처럼 모든 연결을 이차원 배열의 형태로 먼저 입력을 받아야 한다고 생각했는데 인접에 대한 정보를 모두 주어주기 때문에 그렇게 하지 않아도 된다고 생각했습니다.
2. 방문 처리할 visited 생성
3. for문을 통해서 모든 노드를 방문, 방문을 하지 않은 각각의 노드를 기준으로 dfs 시작
4. 이미 방문했다면 리턴
5. 방문하지 않았다면 방문 체크
6. 연결되어 있는 모든 인접 노드를 dfs로 방문하면서 연결된 모든 노드를 방문하면 1을 리턴
7. 리턴한 1을 ans에 저장
8. 3 ~ 6 반복
9. ans 리턴

 

3. 차근차근 구현하기

import Foundation

var visited = [Bool]()

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    visited = Array(repeating: Bool(), count: n)
    var ans = 0
    for i in 0..<n {
        if !visited[i] {
            ans += dfs(i, n, computers)
        }
    }

    return ans
}

func dfs(_ node: Int, _ n: Int, _ computers: [[Int]]) -> Int {
    if visited[node] == true {
        return 0
    }

    visited[node] = true

    // 한 노드에서 전체 노드 방문
    for adj in 0..<n {
        // 연결되어 있는 인접 노드라면 인접노드를 기준으로 dfs 시작
        if computers[node][adj] == 1 {
            dfs(adj, n, computers)
        }
    }
    
    // 연결되어 있는 모든 노드를 방문한 것을 1로 리턴
    return 1
}

 

4. 피드백

• 함수를 정의할 때 처음 입력으로 주어지는 변수를 한꺼번에 넣어서 처리하면 더 빠르게 구현할 수 있다는 것을 배웠습니다.