[Level 3 / 너비 우선 탐색] 네트워크 + 예제 + Swift

네트워크

네트워크

너비 우선 탐색

너비 우선 탐색은 시작점을 방문한 후 인접한 모든 점들을 우선 방문하는 방법이다. 더이상 방문하지 않은 점이 없을 때까지 방문하지 않은 모든 점들에 대해서도 너비 우선 탐색을 적용한다. 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

경로 예제

참고사이트를 참고하였다.

지구에서 한국, 미국, 영국 그리고 각각 [서울,부산,광주][LA, 뉴욕, 시카고] [런던, 리버풀, 멘체스터] 도시들이 있다. 지구 → 한국 → 미국 → 영국 → 서울...순으로 탐색하는 방법이 너비 우선 탐색이다.

let n = 13
let world = ["지구","한국","미국","영국","서울","부산","광주","뉴욕","LA","시카고","런던","맨체스터","리버풀"]

경로 예제 풀이

이름 대신 해당 인덱스로 작성한다.

지구 = 0 ,
한국 = 1, 미국 = 2, 영국 = 3,
서울 = 4, 부산 = 5, 광주 = 6,
뉴욕 = 7, LA = 8, 시카고 = 9,
런던 = 10, 맨체스터 = 11, 리버풀 = 12

모든 연결들을 표시하면 아래와 같다.

let allConnections: [[Int]] = [[0,1], [0,2], [0,3],
                               [1,4], [1,5], [1,6],
                               [2,7], [2,8], [2,9],
                               [3,10], [3,11], [3,12]]

점에 대한 연결을 방문했는지에 대한 visited 이중 배열과, 정점의 순서들을 담을 큐를 만든다. 큐에는 시작점인 0을 넣어준다.

var queue: [Int] = [0]
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: n)

너비 우선 탐색의 핵심은 while문을 이용해 큐가 없을 때까지 반복하는 것이다. 가장 첫번째 숫자를 꺼낸 후 첫번째 숫자와 연결된 숫자를 큐에 담는다. 방문했을 때는 담지 않아 무한 루프를 방지한다.

func bfs(_ queue:inout [Int], _ visited:inout [[Bool]]) {
    while !queue.isEmpty {
        let first = queue.removeFirst()
        print(world[first])
        
        for connection in allConnections {
            if connection[0] == first && !visited[first][connection[1]] {
                visited[connection[1]][first] = true
                visited[first][connection[1]] = true
                queue.append(connection[1])
            }
            
            if connection[1] == first && !visited[first][connection[0]] {
                visited[first][connection[0]] = true
                visited[connection[0]][first] = true
                queue.append(connection[0])
            }
        }
    }
}

world[first]를 출력한 결과, 지구 → 한국 → 미국 → 영국 → 서울...순으로 출력된다.

bfs(&queue, &visited)

네트워크 문제 나의 풀이

위에서 푼 방식과 동일하게 하였다. visited배열은 이중배열이 아닌 일반 배열로 만들었고, queue는 필요없어서 뺐다. 연결되면 visited배열의 해당 자리가 true로 바뀌고, 연결된 컴퓨터중에 방문 안된 것을 방문하면서 true로 바꾼다. 연결이 끝나면, 새로운 출발점에서 다시 연결을 시작한다. 스스로 풀어서 너무 행복하고 뿌듯하다.😆

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

참고사이트 - 너비 우선 탐색 예제

[그림 출처 : https://ko.wikipedia.org/wiki/너비우선탐색]