[Algorithm] 백준 - 13023번 ABCDE (Swift)

문제 소개

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

 

문제풀이

문제를 보고 가장 먼저 연결리스트가 떠올랐다. 연결리스트로 쭉 따라가서 depth가 5가 되면 1을 출력하면 된다는 것을 생각했다.

import Foundation

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (nm[0], nm[1])

var people = [Int: [Int]]()

for i in 0..<n {
    people[i] = []
}

for _ in 0..<m {
    let ab = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (ab[0], ab[1])
    
    people[a]?.append(b)
    people[b]?.append(a)
}

var visited = Array(repeating: false, count: n)

func dfs(_ depth: Int, _ friends: [Int]){
    if depth == 5 {
        print(1)
        exit(0)
    }
    
    for friend in friends {
        if !visited[friend]{
            visited[friend] = true
            dfs(depth + 1, people[friend] ?? [])
            visited[friend] = false
        }
    }
}

for i in 0..<n {
    visited[i] = true
    dfs(1, people[i] ?? [])
    visited[i] = false
}

print(0)