백준 - 트리의 부모 찾기 (11725)

let N = Int(readLine()!)!
var tree: [[Int]] = Array(repeating: [], count: N+1)
var visited = Array(repeating: false, count: N+1)
var answer = Array(repeating: 0, count: N+1)
var result = ""
// 트리 (인접리스트) 데이터 저장
for _ in 0..<N-1 {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    tree[input[0]].append(input[1])
    tree[input[1]].append(input[0])
}

// DFS 실행하면서 부모 노드 찾기
dfs(1)

// 정답 출력
for i in 2...N {
    result += "\(answer[i])\n"
}

print(result)

func dfs(_ num: Int) {
    visited[num] = true
    for next in tree[num] {
        if !visited[next] {
            answer[next] = num
            dfs(next)
        }
    }
}

트리 구현과 관련된 기본적인 문제였다.

이 문제의 입력값에서 부모-자식 관계를 따로 알려주지 않았기 때문에 양방향 에지로 간주하고 입력 받은 두 노드의 리스트에 모두 노드를 추가한다.