[Swift][BFS] 백준 16940번 (BFS 스페셜 저지)

요구능력

BFS와 정렬

 

문제설명

일반적인 BFS문제에 주어진 방문순서대로 방문이 가능한지를 판별하는 문제이다.

간선정보가 주어진다면 인접리스트를 고려해봐야한다.

그래서 인접리스트를 구현했고,

이 인접리스트에 따라서 BFS탐색을 해준다.

1부터 시작한다고 했으므로 1부터 시작해주고 result에는 BFS탐색순서대로 탐색하는 노드들을 저장한다.

 

우리는 주어진 BFS의 방문순서가 가능한것인지 아닌지를 판별해야한다.

그렇기 때문에 주어진 BFS의 방문순서대로 방문을 해보고 되면 1을 출력하고 안되면 0을 출력해야한다.

그래서 주어진 BFS의 방문순서대로 우선순위를 부여해서 먼저 방문해야하는 노드가 있다면 먼저 방문해줘야한다.

우선순위의 경우 0이아닌 1부터 저장하기위해서 i + 1로 해준것이고 i로해도 딱히 상관없을것이다.

이제 인접리스트에서 BFS의 우선순위 순서대로 처리해주기 위해서는 노드의 순서에따라 인접리스트의 노드들을 정렬해줘야한다.

현재노드에서 인접한 노드들을 우선순위별로 정렬하면 된다.

다른언어에서는 모르겠지만 Swift에서는 간편한 정렬기능인 sort()함수를 제공하고 있으므로 간단하게 구현이 가능하다.

 

알아두면 좋은점++) 처음에 그냥 퀵정렬로 했다가 메모리초과가 발생했는데, sort함수 사용하니까 간단하게 구현이 됬다.

퀵정렬의 경우 게속해서 return을 하기 때문에 캐시메모리가 많이 쓰여서 그런거란다.

결국, C++ STL에서 제공하는 sort()와 Swift에서 제공하는 sort()는 비슷한 알고리즘을 가진것같다.

둘 다 O(nlogn)의 시간복잡도를 가진다.

어중간하게 정렬 구현하는것보다는 Swift의 내장함수인 sort()를 사용하는게 왠만해서는 가장 빠를것이다.

 

인접리스트

for _ in 0..<n - 1{
    let a = readLine()!.split(separator: " ").map{Int(String($0))!}
    graph[a[0]].append(a[1])
    graph[a[1]].append(a[0])
}

 

BFS 탐색

func bfs(){
    var queue = [Int]()
    var visited = Array(repeating: false, count: n + 1)
    
    queue.append(1)
    visited[1] = true
    result.append(1)
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        for i in graph[pop]{
            if !visited[i]{
                queue.append(i)
                visited[i] = true
                result.append(i)
            }
        }
        
    }
}

 

우선순위 부여

for i in 0..<order.count{
    bfsOrder[order[i]] = i + 1
}

 

우선순위에 따른 노드의 정렬

for i in 1...n{
    graph[i].sort{bfsOrder[$0] < bfsOrder[$1]}
}

 

후기

우선순위를 정해야한다는 부분만 제외하면 간단한 문제인것같다.

 

코드

import Foundation
let n = Int(String(readLine()!))!
var graph = Array(repeating: [Int](), count: n + 1)
for _ in 0..<n - 1{
    let a = readLine()!.split(separator: " ").map{Int(String($0))!}
    graph[a[0]].append(a[1])
    graph[a[1]].append(a[0])
}
var order = readLine()!.split(separator: " ").map{Int(String($0))!}
var bfsOrder = Array(repeating: -1, count: order.count + 1)
var result = [Int]()

func bfs(){
    var queue = [Int]()
    var visited = Array(repeating: false, count: n + 1)
    
    queue.append(1)
    visited[1] = true
    result.append(1)
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        for i in graph[pop]{
            if !visited[i]{
                queue.append(i)
                visited[i] = true
                result.append(i)
            }
        }
        
    }
}
for i in 0..<order.count{
    bfsOrder[order[i]] = i + 1
}

for i in 1...n{
    graph[i].sort{bfsOrder[$0] < bfsOrder[$1]}
}

bfs()

if result == order {
    print(1)
}else{
    print(0)
}