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

요구능력 : DFS 재귀

 

코드설명 : 

 

네트워크가 따로따로(?)있는게 몇개인지 구하는 문제이다.

예를 들어서 1번과 2번이 연결되어 있고 3번은 따로있으면 네트워크는 2개이다.

만약 1번과 2번과 3번이 모두 연결되어있지 않으면 네트워크는 3개이다

1번과 2번과 3번이 모두 연결되어있으면 네트워크는 1개이다.

 

나는 우선 연결그래프를 만들어주었다.

이렇게 노드의 개수와 연결된 간선이 주어지는 경우에는 연결그래프를 만들어주고 문제를 푸는게 좋다.

만약 입출력 예의 1번같은 경우에는 graph에 다음과 같이 들어갈 것이다.

graph = [[0,1], [0,1], [2]] 

나는 노드를 0번부터 세어주었다.

그래서 0번노드는 0번과 1번이 연결되어있고, 1번노드도 0번과 1번이 연결되어있고, 2번노드는 2번 자신과만 연결되어있다는 결과가 도출된것이다.

//graph = [[0,1], [0,1], [2]]
    for i in 0..<n{
        for j in 0..<computers[i].count{
            if computers[i][j] == 1{
                graph[i].append(j)
            }
            
        }
    }

 

그래프를 구해주었으면 서로 연결을 해주면 된다.

나는 for문을 이용해서 방문하지 않은 노드를 하나씩 넣어주면서 count를 했다.

이렇게 하면 dfs()함수내에서 연결된 노드는 이미 방문이 되어있기 때문에 연결되지 않은 노드들만 방문할 수 있다.

예를 들어 for문에서 dfs(0)이 들어가면 "0"을 방문하고 dfs()함수내의 for문을 통해 "0"과 연결된 노드들을 방문하게된다.

    var visited = Array(repeating: false, count: n)
    var count = 0
    func dfs(_ insu: Int){
        visited[insu] = true
        for i in graph[insu]{
            if !visited[i]{
                visited[i] = true
                dfs(i)
            }
        }
    }
    for i in 0..<n{
        if !visited[i]{
            dfs(i)
            count += 1
        }
    }

 

 

후기 : 대표적인 DFS문제의 유형 중 하나로 백준의 연결요소의 개수와 유사한문제 같다.

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var graph = Array(repeating: [Int](), count: n)
    
    //graph = [[0,1], [0,1], [2]]
    for i in 0..<n{
        for j in 0..<computers[i].count{
            if computers[i][j] == 1{
                graph[i].append(j)
            }
            
        }
    }
    
    var visited = Array(repeating: false, count: n)
    var count = 0
    func dfs(_ insu: Int){
        visited[insu] = true
        for i in graph[insu]{
            if !visited[i]{
                visited[i] = true
                dfs(i)
            }
        }
    }
    for i in 0..<n{
        if !visited[i]{
            dfs(i)
            count += 1
        }
    }
    
    
    
    return count
}