[백준-파이썬] 11725: 트리의 부모 찾기

문제 보러 가기

접근

일단 인접한 노드들을 저장해주었다. 어디가 부모인지, 어디가 자식인지 모르니까 일단은 방향 없이 모두~
그리고 루트를 1로 삼고 거기에서부터 쭉~ 자식을 보러 갔다.
부모를 저장하는 리스트를 만들어서 부모 노드가 몇번 노드인지 저장해줬다.
인접한 노드들을 쭉~ 보되 이미 방문 체크가 되었다면 보지 않았다. 이미 방문 체크가 되었다면, 자식이 아니라 부모라는 뜻이니까..

코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)

N = int(input())
adj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

tree_parent = [0] * (N + 1)


def search(curr_idx):
    for a in adj[curr_idx]:
        if visit[a] == True:
            continue
        tree_parent[a] = curr_idx

        visit[a] = True
        search(a)


visit = [False] * (N + 1)
# 루트 1로 삼고
visit[1] = True
search(1)

for i in range(2, N + 1):
    print(tree_parent[i])

배운 점

노드의 개수가 최대 10만 개이다. 최악의 경우에는 search()가 10만 번 깊이 들어간다.
그래서 sys.setrecursionlimit(10 ** 5)를 해주었는데, 처음에는 습관적으로..(백준 홈페이지 안내(?)에도 그렇게 되어 있어서) sys.setrecursionlimit(10 ** 6)으로 했다. 그랬더니 pypy3에서 메모리 초과가 나왔다.ㅠ
접근부터 틀린건가 고민하면서 질문 검색을 보니, 10**5로 바꾸면 맞는다는 답변이 있어서 바꾸어 보니 맞았다.
그만큼 미리 스택 영역의 메모리를 잡아둔다는 뜻이라서 메모리 초과가 나온 거라는 안내도 있었다.
같은 코드를 돌리면 pypy3는 시간은 빠른데 메모리를 더 많이 차지하곤 하는 것 같다.. 그래서 이런 경우도 있다는 걸 배웠다..!
평소에 문제 풀 때 시간은 고려하는데, 메모리를 잘 생각하지 않았다.ㅠㅠ 생각해야지..