SWEA_5174_subtree

특정한 노드를 루트로 하는 서브 트리에 속한 노드의 개수를 알아내는 프로그램을 만드시오.

문제를 보고 든 생각🙂

해당 노드를 기준으로 중위탐색, 전위탐색, 후위탐색 어떤 것을 써도 될 것 같다.

런타임 에러가 발생한 코드😥

T = int(input())

def preorder(node_idx):
    global result
    # 인덱스의 유효성 검사
    if 1 <= node_idx and node_idx <= E + 1:
        result += 1
        # 왼쪽 자식으로 탐색 진행
        preorder(left[node_idx])
        # 오른쪽 자식으로 탐색 진행
        preorder(right[node_idx])

for tc in range(1, T + 1):
    # E: 간선의 개수
    # N: 기준 노드 번호
    E, N = map(int, input().split())

    # 연결 정보를 저장할 2개의 배열 선언 (노드의 번호는 1번부터 E + 1번까지 존재한다)
    # 1 <= E <= 1000
    left = [0] * 1001
    right = [0] * 1001

    # 간선 정보를 저장해봅시다.
    data = list(map(int, input().split()))
    for i in range(0, 2 * E, 2):
        parent_idx = data[i]
        child_idx = data[i + 1]
        if left[parent_idx] == 0:
            left[parent_idx] = child_idx
        else:
            right[parent_idx] = child_idx

    # N번 노드를 기준으로 탐색해봅시다.
    result = 0
    preorder(N)
    print(f"#{tc} {result}")

통과한 코드😁

T = int(input())

def preorder(node_idx):
    global result
    # 인덱스의 유효성 검사
    if 1 <= node_idx and node_idx <= E + 2:
        result += 1
        # 왼쪽 자식으로 탐색 진행
        preorder(left[node_idx])
        # 오른쪽 자식으로 탐색 진행
        preorder(right[node_idx])

for tc in range(1, T + 1):
    # E: 간선의 개수
    # N: 기준 노드 번호
    E, N = map(int, input().split())

    # 연결 정보를 저장할 2개의 배열 선언 (노드의 번호는 1번부터 E + 1번까지 존재한다)
    # 1 <= E <= 1000
    # 1 <= N <= E + 1
    left = [0] * (E + 2)
    right = [0] * (E + 2)

    # 간선 정보를 저장해봅시다.
    data = list(map(int, input().split()))
    for i in range(0, 2 * E, 2):
        parent_idx = data[i]
        child_idx = data[i + 1]
        if left[parent_idx] == 0:
            left[parent_idx] = child_idx
        else:
            right[parent_idx] = child_idx

    # N번 노드를 기준으로 탐색해봅시다.
    result = 0
    preorder(N)
    print(f"#{tc} {result}")

• 런타임 에러가 발생하는 경우는?

  1. 배열에 할당된 크기를 넘어서 접근했을 때
  2. 전역 배열의 크기가 메모리 제한을 초과할 때
  3. 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
  4. 0으로 나눌 떄
  5. 라이브러리에서 예외를 발생시켰을 때
  6. 재귀 호출이 너무 깊어질 때
  7. 이미 해제된 메모리를 또 참조할 때

• 내 코드에서 런타임 에러가 발생했던 이유

  노드의 개수에 대한 조건은 다음과 같다. 1 <= N <= E + 1
  간선의 개수에 대한 조건은 다음과 같다. 1 <= E <= 1000
  위 두 조건을 합쳐, 노드 개수에 대한 조건을 수로 표현하면 다음과 같다. 1 <= N <= 1001
  즉, 노드의 최대 개수는 1001개이다.

  런타임 에러를 발생시킨 코드를 보면 left와 right 배열의 길이를 1001로 설정하였는데, 노드 번호는 1부터 시작하기 때문에 0번 인덱스를 더한 1002로 설정해주었어야 했다.

  길이를 1002로 설정한 코드는 런타임 에러를 발생하지 않고 pass할 수 있었다.

  물론, 1 <= N <= E + 1 조건을 활용하여 배열의 길이를 E + 2만큼 설정해주는 것이 탄력적이지 않나 싶다.

• 간선의 개수 = 노드의 개수 - 1