백준 tree 구현 (TIL)

안녕하세요! 오늘은 Tree 의 모든 순회 방법들을 swift 코드로 구현해보려고 합니다!! 이제 슬슬 문법도 편해지고 알고리즘을 구성하는
방법들이 눈에 익기 시작하네요! 골드 5단계이긴 하지만 물골드라고 생각했던 저에게 발전해나가는 제 모습이 보여 재밌는 시간이네요! 

오늘은 그래서 문제 1991 번 문제를 해결해보려고 합니다! 예에에에전에 java 로 트리를 구현했던 기억이 있어서 약간은 수월했던 문제입니다! 그럼 설명들어갑니다! 일단 트리의 순회에는 3가지 방법이 있습니다!

전위 순회, 중위 순회, 후위 순회 

이렇게 3가지 방법이 있는데 전위 순회는 루트노드를 먼저 방문하는 방법입니다! 

루트 -> 왼쪽 -> 오른쪽 순으로 모든 트리를 순회한다고 생각하시면 됩니다!! 

 

중위순회는 간단하게 하면 왼-> 루 -> 오  순서이구요! 

마지막으로 후위 순회는 왼 -> 오 -> 루 순서입니다! 

 

이제는 1991번에 필요한 개념을 얼추 아셨습니다! 문제를 보면 입력과 , root, left, right 를 돌아 순회 방법에 따라 전체 노드를 출력하게 됩니다! 
그래서 제가 접근한 방법은 일단 Node struct 를 만듭니다! 그안에서 왼, 오 를 만들어놓을거에요! 그리고 반복해서 받아야하는 입력값이 있기 때문에 for 문을 사용해서 입력을 반복해줍니다! 여기서 중요한건 딕셔너리로 루트에 따르는 자식 노드들을 저장하고있을겁니다! 문법이 기억이 안났어서 조금 찾아보며 했습니다 ㅎㅎ 그래서 첫번째 인덱스가 루트니까 루트 = 자식(왼, 오) 가 있다. 이런식으로 잡고 따로 재귀함수를 구현해서 . 이나올때까지 재귀를 통해 반복해주었습니다! . 이 나오면 리턴! 함수끝!! 이런식으로요! 

그렇게 3개의 함수를 만들어서 루트를 A 로 달아주고 출력해보면?! 결과값이 나올겁니다! 이렇게 약간은 편하게 구현했던것 같습니다! 그럼 소스코드 보여드릴게요! 

import Foundation


struct Node{
    let left : String
    let right : String
    
}

let N = Int(readLine()!)!
var tree : [String : Node] = [:]

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map{String($0)}
    tree[input[0]] = Node(left: input[1], right: input[2])
    
    //이제 딕셔너리에다가 루트랑 레프트 라이트 저장한거임
    
}

func preorder(_ t : String){
    
    if t == "."{
        return
    }
    print(t,terminator: "")
    preorder(tree[t]!.left)
    preorder(tree[t]!.right)
    
}

func inorder(_ t : String){
    if t == "."{
        return
    }
    inorder(tree[t]!.left)
    print(t,terminator: "")
    inorder(tree[t]!.right)
    
}

func postorder(_ t :String){
    if t == "."{
        return
    }
    postorder(tree[t]!.left)
    
    postorder(tree[t]!.right)
    print(t,terminator: "")
}





let orders = [preorder,inorder,postorder]
orders.forEach{
    $0("A")
    print()
}

 

그럼 오늘도 알고리즘 끝~