[프로그래머스] DFS / BFS - 네트워크

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

 

입력 & 출력

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때,
네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

풀이

컴퓨터가 서로 연결되었다면 true, 아니라면 false다
depth 방문한 네트워크를 기록한다

컴퓨터 수만큼 반복하는데, 방문한 적 없는 네트워크에서 탐색을 시작한다
방문한 컴퓨터가 1 (다른 컴퓨터와 연결된 상태)인 경우와 탐색을 아직 하지 않은 곳이라면 재탐색을 시작한다
만약 네트워크가 전부 연결되었을 경우, depth는 전부 true 임으로
네트워크 개수 (count)는 한 번만 기록된다

 

Swift 전체 코드

var depth = Array.init(repeating: false, count: n)
var count = 0

func dfs(_ visited: Int,_ link : [Int]) {
    depth[visited] = true // 방문 표시
    
    for j in 1..<link.count {
        if link[j] == 1 && depth[j] == false{
            dfs(j,computers[j])
        }
    }
}

for i in 0..<computers.count {
    if depth[i] == false {  // 방문한 적이 없는 경우
        dfs(i,computers[i])
        count += 1 // 단절된 네트워크임으로 총합에 1을 더해준다
    }
}

return count

 

풀긴 풀었는데 3중문으로 풀어서.. 슬프다
이후 개선할 예정