[알고리즘] tree 문제풀이

 

 

위 트리를 in-order 형식으로 순회할 경우 SOFTWARE 라는 단어를 읽을 수 있다.

아래 트리를 in-order 형식으로 순회했을때 나오는 단어를 출력하라.

 

위의 예시에서,  알파벳 ‘F’가 2번 정점에 해당하고 두 자식이 각각 알파벳 ‘O’인 4번 정점과 알파벳 ‘T’인 5번 정점이므로 “2 F 4 5”로 주어진다. 알파벳 S는 8번 정점에 해당하므로 “8 S” 로 주어진다.

 

-출처 SW ACADEMY-

[입력]

총 10개의 테스트 케이스가 주어진다. (총 테스트 케이스의 개수는 입력으로 주어지지 않는다) 각 테스트 케이스의 첫 줄에는 트리가 갖는 정점의 총 수 N(1≤N≤100)이 주어진다. 그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다. 정점 정보는 해당 정점의 문자, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점 번호 순서로 주어진다. 정점 번호는 1부터 N까지의 정수로 구분된다. 정점 번호를 매기는 규칙은 위 와 같으며, 루트 정점의 번호는 항상 1이다.

 

[입력]

 

8  #첫 번째 케이스의 N

 

1 W 2 3
2 F 4 5
3 R 6 7
4 O 8
5 T
6 A
7 E
8 S

 

[출력]
#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 답을 출력한다.

 

#1 SOFTWARE
#2 COMPUTER_SCIENCE_AND_ENGINEERING

 

---

알고리즘 문제 풀이

# 트리 순회 함수
def in_order_traversal(node):
    global result
    if node:
        # 왼쪽 자식 노드 순회
        in_order_traversal(tree[node][1])
        # 현재 노드의 문자 추가
        result += tree[node][0]
        # 오른쪽 자식 노드 순회
        in_order_traversal(tree[node][2])

# 총 테스트 케이스 수
T = 10

# 각 테스트 케이스에 대한 처리
for test_case_num in range(1, T + 1):
    # 트리의 정점 수
    N = int(input())
    # 각 정점의 정보를 저장할 딕셔너리
    tree = {}
    # 트리 정보 입력 받기
    for _ in range(N):
        node_info = input().split()
        node_number = int(node_info[0])
        left_child = int(node_info[2]) if len(node_info) > 2 else None
        right_child = int(node_info[3]) if len(node_info) > 3 else None
        tree[node_number] = (node_info[1], left_child, right_child)
    
    # 결과 초기화
    result = ""
    # 루트 노드부터 in-order 순회 시작
    in_order_traversal(1)
    
    # 결과 출력
    print(f'#{test_case_num} {result}')

1. for test_case_num in range(1, T + 1):: 테스트 케이스의 번호를 1부터 T까지 반복합니다.
2. N = int(input()): 각 테스트 케이스의 트리에 포함된 정점의 수를 입력 받습니다.
3. tree = {}: 트리를 표현하기 위한 딕셔너리를 초기화합니다.
4. for _ in range(N):: 입력 받은 정점의 수만큼 반복하여 각 노드의 정보를 입력 받습니다.
5. node_info = input().split(): 각 노드의 정보를 입력 받은 후 공백으로 분리하여 리스트 node_info에 저장합니다.
6. node_number = int(node_info[0]): 노드 번호를 정수로 변환하여 저장합니다.
7. left_child = int(node_info[2]) if len(node_info) > 2 else None: 왼쪽 자식 노드의 번호를 추출합니다. 리스트의 길이가 3 이상인 경우에만 해당 노드가 존재하므로 길이를 확인한 후 정수로 변환합니다.
8. right_child = int(node_info[3]) if len(node_info) > 3 else None: 오른쪽 자식 노드의 번호를 추출합니다. 리스트의 길이가 4 이상인 경우에만 해당 노드가 존재하므로 길이를 확인한 후 정수로 변환합니다.
9. tree[node_number] = (node_info[1], left_child, right_child): 트리 딕셔너리에 노드 정보를 저장합니다. 노드 번호를 키로 하고, 해당 노드의 문자와 자식 노드의 번호를 튜플로 묶어 값으로 저장합니다.
10. result = "": 결과를 저장할 빈 문자열을 초기화합니다.
11. def in_order_traversal(node):: 중위 순회 함수를 정의합니다. 이 함수는 내부 함수로 구현되어 있습니다.
12. nonlocal result: 중위 순회 함수 내에서 전역 변수 result를 수정하기 위해 nonlocal 키워드를 사용합니다.
13. if node:: 현재 노드가 존재하는 경우에만 순회를 수행합니다.
14. in_order_traversal(tree[node][1]): 왼쪽 자식 노드를 방문합니다.
15. result += tree[node][0]: 현재 노드의 문자를 결과에 추가합니다.
16. in_order_traversal(tree[node][2]): 오른쪽 자식 노드를 방문합니다.
17. in_order_traversal(1): 루트 노드부터 중위 순회를 시작합니다.
18. print(f'#{test_case_num} {result}'): 결과를 출력합니다. 테스트 케이스 번호와 결과를 공백으로 구분하여 출력합니다.

---

TREE

    tree = {}
    for _ in range(N):
        node_info = input().split()
        
        # 노드 번호, 문자, 왼쪽 자식 번호, 오른쪽 자식 번호 파싱
        node_number = int(node_info[0])
        left_child = int(node_info[2]) if len(node_info) > 2 else None
        right_child = int(node_info[3]) if len(node_info) > 3 else None
        
        # 트리에 노드 정보 저장
        tree[node_number] = (node_info[1], left_child, right_child)

OR

tree = {}
    for _ in range(N):
        node_info = input().split()
        tree[int(node_info[0])] = (node_info[1], int(node_info[2]), int(node_info[3]) if len(node_info) > 3 else None)

1. node_number = int(node_info[0]): 이 코드는 입력으로 받은 트리의 각 노드 정보에서 노드 번호를 가져옵니다. node_info[0]은 각 노드 정보의 첫 번째 요소로, 이 요소에는 노드 번호가 들어 있습니다. 이 값을 정수형으로 변환하여 node_number 변수에 저장합니다.
2. left_child = int(node_info[2]) if len(node_info) > 2 else None: 이 코드는 해당 노드의 왼쪽 자식 노드 번호를 가져옵니다. 노드 정보에 왼쪽 자식 노드가 있는지 확인하기 위해 len(node_info) > 2 조건을 사용합니다. 만약 왼쪽 자식 노드가 있다면 node_info[2]에서 그 번호를 가져와서 정수형으로 변환한 뒤 left_child 변수에 저장합니다. 왼쪽 자식 노드가 없으면 None 값을 할당합니다.
3. right_child = int(node_info[3]) if len(node_info) > 3 else None: 이 코드는 해당 노드의 오른쪽 자식 노드 번호를 가져옵니다. 왼쪽 자식 노드와 같은 방식으로 처리합니다. 오른쪽 자식 노드 번호가 있는지 확인하기 위해 len(node_info) > 3 조건을 사용하고, 있다면 해당 번호를 가져와서 정수형으로 변환한 뒤 right_child 변수에 저장합니다. 오른쪽 자식 노드가 없으면 None 값을 할당합니다.
4. tree[node_number] = (node_info[1], left_child, right_child): 이 코드는 트리의 각 노드에 대한 정보를 사전 형태로 저장합니다. node_info[1]은 해당 노드의 문자 정보를 나타내며, 앞서 구한 왼쪽 자식 노드 번호와 오른쪽 자식 노드 번호를 튜플로 묶어서 저장합니다. 이를 통해 각 노드 번호를 기준으로 해당 노드의 문자 정보와 자식 노드들의 번호를 쉽게 확인할 수 있습니다.

---

in_order_traversal(1)

   # 결과 초기화
    result = ""
    # in-order 순회를 통해 단어 생성
    def in_order_traversal(node):
        nonlocal result
        if node:
            in_order_traversal(tree[node][1])
            result += tree[node][0]
            in_order_traversal(tree[node][2])
    in_order_traversal(1)

 

 

트리에서 루트 노드부터 시작하여 중위 순회(in-order traversal)를 수행하는 함수. 중위 순회는 왼쪽 자식 노드를 먼저 방문한 뒤 현재 노드를 처리하고, 마지막으로 오른쪽 자식 노드를 방문하는 방식으로 트리를 순회. 일반적으로 트리의 순회는 루트 노드에서 시작하며, 이 경우에는 루트 노드의 번호가 1이므로 in_order_traversal(1)은 루트 노드부터 순회를 시작함을 의미.

---

노드를 표기하는 방식

 

 

여기서 "노드 번호"는 각 노드를 식별하는 번호이며, "값"은 해당 노드의 데이터 값을 나타낸다.. "왼쪽 자식 노드 번호"와 "오른쪽 자식 노드 번호"는 각각 해당 노드의 왼쪽 자식과 오른쪽 자식을 가리키는 것이다. 만약 자식이 없는 경우에는 None으로 표시.

 

노드 1: (1, 값, 2, 3)

노드 2: (2, 값, 4, 5)

노드 3: (3, 값, None, None)

노드 4: (4, 값, None, None)

노드 5: (5, 값, None, None)