[백준 알고리즘] - 트리의 부모 찾기 (11725번) with Python

📎 간략한 문제 정리

• 트리의 루트가 1이고 나머지 요소들의 연결 상태가 주어질 때, 나머지 요소들의 부모 노드를 출력하는 코드를 작성합니다.

📈 문제 분석

• 연결 상태를 관찰하며 각 요소의 부모 노드를 출력하는 문제입니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• dictionary를 통해 연결 상태를 정의하고, 각 요소별로 부모 노드를 검색하면 O(1)으로 탐색 가능합니다.

💻 풀이한 코드

from sys import stdin, setrecursionlimit
from collections import defaultdict
setrecursionlimit(10**9)
input = stdin.readline
N = int(input())
adj = defaultdict(list)
parents = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
for _ in range(N-1):
    node1, node2 = map(int, input().split())
    adj[node1].append(node2)
    adj[node2].append(node1)
def find_parent(node):
    adj_list = adj[node]
    visited[node] = True
    for adj_child in adj_list:
        if not visited[adj_child]:
            parents[adj_child] = node
            find_parent(adj_child)
find_parent(1)
print('\n'.join(map(str, parents[2:])))

📝 해결 과정에서 만난 문제, 고민들

• 런타임 에러 발생:

  백준 알고리즘에서 일반적으로 런타임 에러는 인덱스 오류에서 발생하기 때문에 혹시 노드의 숫자가 1씩 증가하는 구조가 아닌지 생각해봤습니다. 문제에 조건에 나와있지 않기 때문입니다. 하지만 예시를 보면 1씩 증가하는 구조로 되어있고 더 고민해보니 재귀 구조로 작성된 코드이므로 재귀의 깊이에서 문제가 발생하여 재귀 깊이를 sys의 setrecursionlimit로 설정해주어 문제를 해결했습니다. 파이썬으로 재귀의 깊이는 굉장히 얕기 때문에 항상 체크할 필요가 있습니다.

• 메모리 에러 발생:

  런타임 에러가 해결되자마자 메모리 에러가 발생하여 이유를 알 수 없어 질문을 검색해봤습니다. 로직에는 문제가 없지만 pypy로 코드를 실행시킬 경우 메모리 이슈가 발생할 수 있어 python3로 실행시키라는 추천을 봐서 python3로 실행시켜 오류를 해결했습니다. 단순히 pypy가 python3보다 실행 속도가 빠르다고 인식하는 것이 아니라 이 기회에 두 차이를 정확히 짚어보았습니다.

  1. CPython

     C로 구현된 CPython은 인터프리터이면서 컴파일러입니다. 작성한 Python 코드를 bytecode로 컴파일하여 실행합니다. 즉, 코드를 C언어가 아닌 bytecode로 컴파일한 후 해석(interprete)합니다.

  2. PyPy

     PyPy는 JIT(Just In Time) 컴파일을 사용합니다. 프로그램 실행 전에 컴파일 하는 것이 아니라 프로그램 실행 시점에 필요한 부분을 즉석으로 컴파일합니다. 인터프리터 언어의 단점 중 하나가 실행 성능이기 때문에 주로 성능 향상을 목적으로 도입하는 개념입니다. 해석하며 자주 쓰이는 코드를 캐싱하기 때문에 인터프리터 언어의 단점인 느린 실행속도를 향상시킬 수 있습니다.

     실행 속도가 향상되는 반면 위의 캐싱 기능 때문에 당연히 메모리 사용량은 증가합니다.

  결론적으로 아주 간단한 코드에서는 단순한 인터프리터만으로 문제가 없으므로 메모리, 속도 측면에서 Python3가 우세할 수 있고, 복잡한 구조의 코드를 사용할 때에 속도라는 측면에서는 PyPy가 우세합니다.

• 🧐 문제의 정보가 부족하다고 느꼈습니다. 예를 들어, 트리가 끊겨있는 구조가 입력에 존재할 수 있는지 등의 자세한 설명이 없었습니다. 만약 트리가 끊겨있을 수 있다면 단순히 재귀의 조건만 파고드는 것이 아니라 검색 node의 경우를 반복문을 통해 모두 확인해주어야 합니다.

​

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