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

문제

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

프로그래머스

 

풀이

DFS by 재귀

맨 처음엔 간선만 신경을 썼으나, 문제에서 요구하는 '네트워크의 수'는 간선과 아무것도 연결되어있지 않는 노드도 신경을 써서 도출해야 했다.

dfs로 재귀를 통해 연결되어있는 노드를 탐색하면, 연결되어 있는 노드를 끝까지 탐색하도록 했다. 이때 탐색했다는 표시도 동시에 해서 최종적으로 탐색되지 않은 (아무것도 연결되어있지 않은) 노드의 개수를 구할 수 있도록 했다.

간선의 개수는 처음 dfs가 시작되는 시점에 count+1을 해주었다. (재귀적으로 몇 번 들어가는 것과 상관없이 하나의 네트워크를 탐색하기 때문)

 

괜히 복잡하게 푼 것 같다. 정답부터 맞히려는 탓에 효율적으로 못 짠 부분이 많이 보인다.

몇 달 전에 시도했다가 결국 못 풀었던 문제인데, 문제를 맞히니 그래도 공부한 보람이 있구나 싶었다. (사실 DFS의 기본 유형인 것 같긴 하다.) 꾸준히 기초를 더 공부해야겠다.

 

코드

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    func dfs(_ current: (Int,Int)) {
        graph[current.0][current.1] = 0
        graph[current.1][current.0] = 0
        
        for k in 0..<n {
            if graph[current.1][k] == 1 {
                computer[current.1] = true
                computer[k] = true
                dfs((current.1,k))
            }
        }
    }
    
    var graph = computers, network = 0, computer = [Int: Bool]()
    for i in 0..<n {
        computer[i] = false
    }
    
    for i in 0..<n {
        graph[i][i] = 0
    }
    
    for i in 0..<n {
        for j in 0..<n {
            if graph[i][j] == 1 {
                network += 1
                computer[i] = true
                computer[j] = true
                dfs((i,j))
            }
        }
    }
    
    return network + computer.filter{ $0.value == false }.count
}