[Algorithm] 백준 - 11725번 트리의 부모 찾기 (Swift)

문제 소개

연결된 두 노드의 정보를 주고 해당 노드의 부모노드를 구하는 프로그램을 작성하는 문제이다.

문제 풀이

graph에 연결을 저장한 뒤, bfs를 통해 트리구조를 만들었다.

import Foundation

let n = Int(readLine()!)!
var graph = Array(repeating: [Int](), count: n+1)

for _ in 0..<n-1 {
    let info = readLine()!.split(separator: " ").map { Int($0)! }
    graph[info[0]].append(info[1])
    graph[info[1]].append(info[0])
}

var tree = [Int: Int]()
var visited = Array(repeating: false, count: n+1)

func bfs() {
    var queue = [1]
    
    while !queue.isEmpty {
        let poped = queue.removeFirst()
        
        for node in graph[poped] {
            if !visited[node] {
                visited[node] = true
                tree[node] = poped
                queue.append(node)
            }
        }
    }
}

bfs()

for i in 2...n {
    if let root = tree[i] {
        print(root)
    }
}