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

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

프로그래머스

 

2023.07.04 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

서로 연결된 노드들끼리는 1개의 네트워크로 취급할 때 총 네트워크의 개수를 구하는 문제입니다.

DFS, BFS, Union Find 등 다양하게 푸는 방법이 있지만 DFS로 풀어보았습니다.

 

각 노드들끼리의 연결관계가 2차원 배열로 주어지고 앞서 서로 연결된 노드끼리는 1개의 네트워크로 취급하기 때문에 DFS를 사용하여 연결된 노드(컴퓨터)들을 재귀적으로 탐색하여 visited 어레이에 방문한 곳은 true로 기록합니다.

한번 방문한 곳은 다시 방문하지 않도록 하여 중복으로 네트워크 개수를 세는 일을 방지합니다.

 

풀이

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var result: Int = 0
    var visited: [Bool] = Array(repeating: false, count: n)
    
    func dfs(i: Int) {
        visited[i] = true
        let connectedComputers = computers[i]
                
        for (index, isConnected) in connectedComputers.enumerated() {
            if isConnected == 1 && !visited[index] {
                dfs(i: index)
            }
        }
    }
    
    for i in 0..<n {
        if !visited[i] {
            result += 1
            dfs(i: i)
        }
    }
    
    return result
}

 

dfs 함수가 한번 쭉 탐색을 마치면 1개의 네트워크의 탐색을 끝낸 것이고 해당 노드들은 전부 visited에 기록되어 다음 탐색에서 제외되는 구조입니다.

아직 방문하지 않은 노드들을 dfs로 탐색시키면서 result 값을 1씩 증가시키면 네트워크의 개수를 구할 수 있습니다.

 

마무리

기본적인 DFS, BFS 문제였습니다!
visited 처리와 result를 증가시키는 시점이 중요했던 것 같습니다..!