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

문제 소개

https://www.acmicpc.net/problem/16940

bfs 방문 순서가 올바른 순서인지 판별하는 문제이다.
 

문제 풀이

집합을 활용했다. bfs를 수행한뒤 결과값을 집합에 넣는다. 그리고 결과값과 비교한다.

import Foundation

let n = Int(readLine()!)!
var infos = Array(repeating: [Int](), count: n + 1)

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

let check = readLine()!.split(separator: " ").map { Int(String($0))! }
if check[0] != 1 {
    print(0)
    exit(0)
}

var current = 1

var first: Set<Int> = [1]
var second: Set<Int> = [1]
var idx = 0
var cnt = 1
var visited = Array(repeating: false, count: n+1)
visited[1] = true

while n > idx {
    var count = 0
        
    for element in infos[check[idx]] {
        if !visited[element] {
            visited[element] = true
            count += 1
            second.insert(element)
        }
    }
    
    if second.isEmpty { break }
        
    for i in cnt..<cnt+count {
        first.insert(check[i])
    }
    
    if first != second {
        print(0)
        exit(0)
    }
    
    idx += 1
    cnt += count
    first = []
    second = []
}

print(1)