[코독하구만 팀] 2020.01.05(화) - 3주차 개인 결과

- 목표 -

codekodo.tistory.com/12

[코독하구만 팀] 2021.01.05(화) - 3주차 개인 목표

 

LCA(Lowest Common Ancestor) 알고리즘 개념 및 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해봄으로써 알고리즘 동작방식에 대해 알게 되었다. 실습에서 배운 방식으로 백준 문제를 접근하였지만 아직 풀지 못하였다. 다른 방식으로 LCA를 접근해보려고 한다.

 

1. root 찾기

def main():
    n = int(input())
    parent = []
    child = []
    
    for _ in range(n):
        node = list(input().split())
        if node[1] != '.' or node[2] != '.':
            parent.append(node[0])
            child.append(node[1])
            child.append(node[2])
    
    for i in parent:    # 부모 노드가 저장된 리스트의 원소가
        if i not in child:  # 자식 노드가 저장된 리스트에 없으면
            root = i
            break
    
    print(root)

if __name__ == "__main__":
    main()

 

A B C 인 경우 A가 부모 노드, B와 C가 자식 노드이다.

B D . 인 경우 B가 부모 노드, D가 자식 노드이다.

따라서 . 를 1개 이하로 가지고 있다면 부모 노드 - 자식 노드 쌍으로 볼 수 있다.

이후 부모 노드와 자식 노드를 각각 다른 리스트에 저장한다.

부모 노드 리스트의 원소가 자식 노드 리스트에 없으면 이는 루트 노드라고 볼 수 있다.

 

2. 트리 순회

def preorder(node, tree, visit):
    visit.append(node)
    if tree[node][0] != '.':
        preorder(tree[node][0], tree, visit)
    if tree[node][1] != '.':
        preorder(tree[node][1], tree, visit)
    
    return visit

def inorder(node, tree, visit):
    if tree[node][0] != '.':
        inorder(tree[node][0], tree, visit)
    visit.append(node)
    if tree[node][1] != '.':
        inorder(tree[node][1], tree, visit)

    return visit

def postorder(node, tree, visit):
    if tree[node][0] != '.':
        postorder(tree[node][0], tree, visit)
    if tree[node][1] != '.':
        postorder(tree[node][1], tree, visit)
    visit.append(node)

    return visit

def main():
    n = int(input())
    tree = {}
    parent = []
    child = []
    
    for _ in range(n):
        node = list(input().split())
        tree[node[0]] = [node[1], node[2]]  # tree를 구현한다
        if node[1] != '.' or node[2] != '.':
            parent.append(node[0])
            child.append(node[1])
            child.append(node[2])
    
    for i in parent:    # 부모 노드가 저장된 리스트의 원소가
        if i not in child:  # 자식 노드가 저장된 리스트에 없으면
            root = i
            break
    
    visit = []
    print(*preorder(root, tree, visit))

    visit = []
    print(*inorder(root, tree, visit))

    visit = []
    print(*postorder(root, tree, visit))

if __name__ == "__main__":
    main()

 

1번 문제를 풀면서 사용한 root 노드 찾는 코드를 그대로 사용한다.

이후 전위, 중위, 후위 탐색을 진행한다.

전위 탐색의 경우 root > left > right 순으로 방문한다.

중위 탐색의 경우 left > root > right 순으로 방문한다.

후위 탐색의 경우 reft > right > root 순으로 방문한다.

위의 개념을 코드로 구현한다.

 

3. 최소 공통 조상 노드

def preorder(root, tree, visit, depth_list, depth): # 전위탐색을 진행하면서 방문 순서와 탐색 깊이를 저장한다
    visit.append(root)
    depth_list.append(depth)
    depth += 1
    if tree[root][0] != '.':
        preorder(tree[root][0], tree, visit, depth_list, depth)
        visit.append(root)
        depth -= 1
        depth_list.append(depth)
    depth += 1
    if tree[root][1] != '.':
        preorder(tree[root][1], tree, visit, depth_list, depth)
        visit.append(root)
        depth -= 1
        depth_list.append(depth)

    return visit, depth_list

def main():
    n = int(input())
    tree = {}
    parent = []
    child = []
    
    for _ in range(n):
        node = list(input().split())
        tree[node[0]] = [node[1], node[2]]  # tree를 구현한다
        if node[1] != '.' or node[2] != '.':
            parent.append(node[0])
            child.append(node[1])
            child.append(node[2])
    
    for i in parent:    # 부모 노드가 저장된 리스트의 원소가
        if i not in child:  # 자식 노드가 저장된 리스트에 없으면
            root = i
            break

    visit = []
    depth_list = []
    depth = 0
    visit, depth_list = preorder(root, tree, visit, depth_list, depth)
    
    find = list(input().split())    # 질의 노드
    first_index = visit.index(find[0])  # 방문 순서가 저장된 리스트에서 질의 노드를 처음 방문한 index를 찾는다
    second_index = visit.index(find[1])

    if first_index > second_index:  # 탐색을 위해 오름차순으로 정렬해준다
        first_index, second_index = second_index, first_index

    max_depth = depth_list[first_index]
    for i in range(first_index+1, second_index+1): # 주어진 구간 안에서 최대 깊이를 찾는다
        if depth_list[i] < max_depth:
            max_depth = depth_list[i]
    
    max_index = depth_list.index(max_depth) # 최대 깊이의 index를 저장한다

    print(visit[max_index])

if __name__ == "__main__":
    main()

 

1, 2번을 모두 활용한 문제이다.

전위탐색을 통한 노드 방문 순서와 노드의 깊이를 각각 다른 리스트에 저장한다.

주어진 입력 값으로 이를 구해보면 다음과 같다.

방문 순서 : 1 2 4 2 5 2 1 3 1

        깊이 : 0 1 2 1 2 1 0 1 0

 

이후 입력된 질의 노드의 방문 순서 리스트에서의 index 값을 찾아낸다.

주어진 입력값(3, 4)으로 이를 구해보면 다음과 같다.

방문 순서 : 1 2 4 2 5 2 1 3 1

 

이 index 값을 깊이 리스트에서의 탐색 범위로 정하고 범위 이내에서 가장 작은 깊이가 LCA의 깊이가 된다.

  깊이 : 0 1 2 1 2 1 0 1 0

index : 0 1 2 3 4 5 6 7 8

 

따라서 LCA는 방문 순서 리스트의 7번째 원소인 1이 된다.

 

- 깃허브 -

github.com/k906506/2020_Winter_Assemble-And-selfcode

k906506/2020_Winter_Assemble-And-selfcode