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

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

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

 

네트워크 간에 연결이 되어 있는지, 연결된 망이 총 몇 개인지 구하면 되는 문제이다. 

 

문제의 카테고리도 BFS/DFS이기에 두 알고리즘을 이용해서 풀이를 하면 되겠다. 

Set의 intersection을 활용해서도 풀 수 있겠으나, BFS/DFS 문제인 만큼 한 번 충실해보자!

 

문제를 보고 대략적으로 그렸던 그림은 다음과 같다. 

 

1. 먼저 주어진 배열을 기반으로 dictionary 형태의 graph를 생성한다. 

2. DFS를 활용하여 각 Node간 연결되어 있는지 여부를 파악한다. 

3. 동시에 독자적인 네트워크 망을 발견할 때 마다 count에 1씩 더해준다. 

 

바로 코드로 가보자. 

 

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    
    // graph 만들기 
    var graphs = [Int:[Int]]()
    
    for (i,computer) in computers.enumerated() {
        for (j,cpu) in computer.enumerated() {
            if cpu == 1 && i != j {
                if let _ = graphs[i+1] {
                    graphs[i+1]!.append(j+1)
                } else {
                    graphs[i+1] = [j+1]
                }
            }
        }
    }

    // 독립적인 네트워크 망의 개수를 세는 과정
    var visitedNodes = Array(repeating: false, count : n)
    var cnt = 0
    for i in 1...n {
        if !visitedNodes[i-1] {
            visitedNodes[i-1] = true
            cnt += 1
            let indices = DFS(graphs,i)
            for idx in indices {
                visitedNodes[idx-1] = true    
            }
        } 
    }
    
    return cnt
}

// DFS
func DFS(_ graph: [Int:[Int]], _ start: Int) -> [Int] {
    var visited = [Int]()
    var nextNodes = [Int]()
    nextNodes.append(start)
    
    while !nextNodes.isEmpty {
        let next = nextNodes.removeLast() 
        if !visited.contains(next) {
            visited.append(next)
            if let value = graph[next] {
                nextNodes.append(contentsOf: value)
            } else {
                break
            }
        }
    }
    return visited
}

 

DFS 쪽을 보면 문제에서 요구하는 것 이상으로 구현해져있는 것을 볼 수 있다. 

바로 visited를 리스트로 관리하는 부분인데, 문제에서는 개수만 물었기에 위의 독립적인 네트워크 망을 세는 부분을 DFS에 합칠 수도 있을 것 같다. 다만 다른 유형의 문제들에서는 개수가 아닌 그 네트워크(리스트)를 반환하라고 할 수 있기에 해당 방법으로 풀이를 진행했다. 

효율성을 체크하는 문제가 아니기에 다각도로 문제를 바라보았다. 

---

BFS/DFS에 익숙해지려고 프로그래머스의 BFS/DFS 고득점 문제 Kit를 보고 있는데, 완전 익숙해진 것 같지는 않다. 

머릿속으로는 떠오르는데 아직은 조금씩 헤매는 느낌이다. 머릿속에서 그리는대로 바로바로 구현될 수 있게 반복 학습이 필요할 것 같다.