[Swift 백준] 24480 알고리즘 수업 - 깊이 우선 탐색 2

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

 

 

풀이 아이디어 

일반적인 dfs입니다.

인접 정점을 내림차순으로 방문한다는 점을 주의해야하는 문제입니다

재귀로 풀이했습니다.

 

 

풀이

let nmr = readLine()!.split(separator: " ").map{Int($0)!}

let (n,m,r) = (nmr[0],nmr[1],nmr[2])

// []로 repeating하여 생성할 경우 반드시 타입을 선언해야합니다.
var graph: [[Int]] = Array(repeating: [], count: n + 1)

for i in 0..<m {
    let input = readLine()!.split(separator: " ").map{Int($0)!}
    let (a,b) = (input[0],input[1])
    
    //무방향 그래프는 양방향 그래프를 뜻합니다.
    graph[a].append(b)
    graph[b].append(a)
}

var isVisited = Array(repeating: 0, count: n + 1)

var depth = 1

func dfs(node: Int) {
    isVisited[node] = depth
    
    // sorted를 활용해 내림차순으로 접근해줍니다
    for next in graph[node].sorted(by: >) {
        if isVisited[next] == 0 {
            depth += 1
            dfs(node: next)
        }
    }
}

dfs(node: r)

print(isVisited[1...].map{String($0)}.joined(separator: "\n"))