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

요구능력

DFS와 정렬

 

문제풀이

https://sapjilkingios.tistory.com/entry/SwiftBFS-%EB%B0%B1%EC%A4%80-16940%EB%B2%88-BFS-%EC%8A%A4%ED%8E%98%EC%85%9C-%EC%A0%80%EC%A7%80

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

위의 BFS스페셜저지와 동일한 문제입니다.

바뀌는점은 BFS -> DFS인것 밖에 없습니다.

 

어려운것없이 1번노드를 먼저방문하도록 dfs(1)로 함수를 호출합니다.

그리고 연결된노드를 깊이우선탐색합니다.

 

DFS()

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

 

후기

BFS스페셜저지에서 DFS로 바꾸기만하면 정답

 

코드

import Foundation
let n = Int(String(readLine()!))!
var arr = [[Int]]()
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 dfsOrder = Array(repeating: -1, count: order.count + 1)
for i in 0..<order.count{
    dfsOrder[order[i]] = i + 1
}
var result = [Int]()
var visited = Array(repeating: false, count: n + 1)
func dfs(_ start: Int){
    visited[start] = true
    result.append(start)
    for i in graph[start]{
        if !visited[i]{
            dfs(i)
        }
    }
}
for i in 1...n{
    graph[i].sort{dfsOrder[$0] < dfsOrder[$1]}
}
dfs(1)

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