[백준 알고리즘] - 트리 순회(1991번) with Swift

문제

 

풀이 과정의 고민

• 시뮬레이션으로 문자열을 직접 탐색하는 것도 방법일 수 있다고 생각했어요. DFS처럼 탐색하지만 탐색 조건을 변경하면서요. 하지만 그런 방식은 상황이 너무 복잡해지고 작은 디테일에서 오류가 쉽게 발생할 수 있다고 생각해서 노드를 직접 만드는 것으로 생각했어요.
• 이 글에서 전위, 중위, 후위 순회에 대한 설명을 하진 않을 계획이에요. 다만, 각 탐색 메서드에서 명백하게 출력의 우선순위를 보여주는 것이 중요하다고 생각해요. 전위는 말 그대로 부모 노드의 데이터를 먼저 보여주는 것, 중위는 왼쪽 노드부터 탐색한 후 부모 노드의 값을 출력해주고 오른쪽 노드를 탐색하는 것처럼이요.
  
  
• 언어를 조금 고민했어요. 파이썬 풀이도 추가로 올릴 예정이지만, 아무래도 Node 클래스를 이용해 풀이하는 데에는 Swift가 더 편하다고 생각했어요. 대신, 백준의 특성상 입력 방식에서 자잘한 오류가 많이 발생했어요.

 

풀이

struct Node {
    let data: String
    let leftNode: String
    let rightNode: String
}
// 전위 순회
func preOrder(node: Node) {
    print(node.data, terminator: "") // terminator ':' not '='
    if node.leftNode != "." {
        preOrder(node: tree[node.leftNode]!)
    }
    if node.rightNode != "." {
        preOrder(node: tree[node.rightNode]!)
    }
}
// 중위 순회
func inOrder(node: Node) {
    if node.leftNode != "." {
        inOrder(node: tree[node.leftNode]!)
    }
    print(node.data, terminator: "")
    if node.rightNode != "." {
        inOrder(node: tree[node.rightNode]!)
    }
}
// 후위 순회
func postOrder(node: Node) {
    if node.leftNode != "." {
        postOrder(node: tree[node.leftNode]!)
    }
    if node.rightNode != "." {
        postOrder(node: tree[node.rightNode]!)
    }
    print(node.data, terminator: "")
}
// 입력
let n = Int(readLine()!)! // Large letter L
var tree: [String:Node] = [:]
for _ in 0..<n {
    let nodes = readLine()!.split(separator: " ") // split option
    tree[String(nodes[0])] = Node(data: String(nodes[0]), leftNode: String(nodes[1]), rightNode: String(nodes[2]))
}
// 실행
let startNode = tree["A"]!
preOrder(node: startNode)
print()
inOrder(node: startNode)
print()
postOrder(node: startNode)

 

 

풀이할 때 생긴 에러

• 백준 알고리즘 말고는 사용할 일이 잘 없는 readLine에서 문제가 발생했어요. 알고리즘 풀이에 주로 사용하는 파이썬의 경우 readline으로 'l'이 소문자인데 Swift의 readline은 readLine으로 대문자 'L'이어서 에러가 발생했어요.
• String을 Split한 결과물은 String이 아니라 Substring이라는 다른 타입이 돼요. Substring에 대한 설명은 Substring 공식문서에서 자세히 볼수 있어요. 결론은 다른 타입이기 때문에 casting이 필요했어요.
• Python의 경우 print()에서 출력 마지막 조건이 (end=" ")인데 Swift는 당연히도 parameter를 ":"로 받기 때문에 (terminator:) 로 해야해요. 습관의 무서움..

 

문제 출처

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