[Algorithm] 백준 - 16964번 DFS 스페셜 저지 (Swift)

문제 해석

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

dfs로 풀라고 만든 문제이다. dfs방문순서가 맞는지 물어보는 문제이다. 보통은 dfs로 결과를 찾아나가는데, dfs자체를 검증하는 문제는 신선했다.

문제 풀이

체크하려는 배열에서 우선순위를 priority 딕셔너리 타입으로 만든다음에 저장한뒤 이 우선순위대로 graph를 재배열 하는 방식으로 풀었다. 그 이후 dfs를 돌려(?) 결과값을 비교했다.

import Foundation

let n = Int(readLine()!)!
var graph = 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])
    graph[a].append(b)
    graph[b].append(a)
}

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

var priority = [Int: Int]()
for i in check.indices {
    priority[check[i]] = i
}

var idx = 0
var visited = Array(repeating: false, count: n+1)

for i in 1...n {
    graph[i].sort(by: { priority[$0]! < priority[$1]! })
}

var answer = [Int]()

func dfs(_ i: Int) {
    if visited[i] { return }
    answer.append(i)
    visited[i] = true
    
    for i in graph[i] {
        if !visited[i] {
            dfs(i)
        }
    }
}

dfs(1)

if answer == check {
    print(1)
} else {
    print(0)
}