트리 부모 찾기 - 질문해서 배운 점들

백준 11725 트리부모찾기! 스마트하신 항해원분이 BFS로 발표해주시는 걸 듣고 그분의 tip(?!)을 적용해서 DFS로도 풀어보려고 했다.

코드 전 손으로 정리해본 내용은 아래와 같다.

예제들 돌려볼 때는 원하는 출력대로 나오는데 메모리 초과라고 뜬다..!

"백준 메모리초과" 라고 검색해보니 꼭 이 문제는 아니더라도 - 방문처리를 해줘야해요 - 이런 조언들이 있었다.

 

나도 그런 부분에서 잘못하고 있는 걸까? 근데 따로 방문처리할 배열같은 걸 만들 필요가 있을까 모르겠다.

왜냐하면 답변으로 사용할 res 배열을 부모 노드 값으로 채워나가고 있고, 이미 방문했으면 0이 아닐 것인데,

if res[child] == 0: 

이렇게 쓰는 것만으로는 뭔가 새는 부분이 있나..?

 

✔︎ 궁금했던 점

 - 아래의 코드에서 "메모리 초과"가 뜬 원인은 무엇일까?

 - 방문처리를 따로 하지 않아서라면, res 배열에 정보가 할당되었는지로 따져보는 것과 어떤 차이를 갖기 때문일까?

import collections
import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())

# 간선 정보들
connect_info = collections.defaultdict(list)
# 결과로 제출할 때 쓸 배열
res = [0] * (n + 1)
# 사용하지 않을 칸을 0이 아닌 값으로 채워두기
res[0] = -1
res[1] = -1

for _ in range(n-1):
    connect = tuple(map(int, sys.stdin.readline().split()))
    connect_info[connect[0]].append(connect[1])
    connect_info[connect[1]].append(connect[0])

def DFS(num):
    if 0 not in res:
        for i in range(2, n+1):
            print(res[i])
        return

    else:
        for child in connect_info[num]:
            if res[child] == 0:
                res[child] = num
                DFS(child)

DFS(1)

 

📝 스마트하신 분한테 질문해서 알게 된 것들

1) 내가 잘못했던 부분 발견

우선 이 분께서도 재귀로 풀어보셨고, 제출이 되었다고 하셨다. 그래서 코드를 공유해주셨는데, 내가 기존에 한 것과 대조해보니까 일단 내가 굳이 필요하지 않은데 작성한 부분이 있다는 것을 알게 되었다. 

이거는 DFS의 종료조건을 써주려고 했던 " if 0 not in res: ~" 부분인데 이게 필요가 없는 부분이었다. 왜냐하면 계속해서 작업할 "else:" 이후의 작업은 connect_info를 다 돌면서 작업을 마치면 어차피 자동 종료될 것이기 때문이었다.

그래서 그 부분을 삭제해서 python3로 제출해봤더니 제출이 되었다..! (+ 근데 pypy로는 안 된다..!)

2) 재귀가 다른 풀이 방식에 비해 더 메모리를 많이 쓴다는 것

stack이나 queue로 풀이 시 메모리 50000kb정도 소모합니다.

재귀로 풀이 시 메모리 150mb 정도 소모합니다. - 이렇게 스마트한 항해원분이 알려주셨다ㅎㅎ

 

얼른 여러 방식의 풀이를 잘 익혀서 내가 풀 수 있는가를 기준으로 방법을 선택하는 것이 아니라, 무엇이 더 효율적인지를 기준으로 풀이 방식을 선택할 수 있는 때가 오면 좋겠다🤓