[질문] 재귀 dfs vs 스택 dfs 차이

[익명(122.39)]

메모리나 시간 복잡도에서 차이가 있음?

- dc official App

[익명(skuld88)]

메모리는 O(V)만큼 더 잡아먹고 시간복잡도는 똑같은데 노드 방문순서가 다름

[익명(122.39)]

O(V) 만큼 더 잡아먹는 게 스택 dfs?? - dc App

[익명(skuld88)]

위상정렬 같은거는 재귀dfs로만 되고 스택dfs로는 안됨

[익명(118.235)]

위상정렬이 재귀 dfs로 하는거야? 큐 써서 bfs 처럼 하는거 아닌교

[익명(122.39)]

나는 위상정렬 heap쓰는디 - dc App

[익명(skuld88)]

두가지 방법 다됨. 재귀 dfs로도 할수 있고 indegree 0인 애들부터 bfs 돌리는거. 하지만 스택dfs는 내가 알기로 안됨

[익명(118.235)]

헐 재귀로도 된다니... 배울게 태산이구나

[익명(222.109)]

엥 상관없지않나??

[익명(hz42nvvfb2jm)]

깊이 깊으면 터지니까 스택으로 하는것도 알아둬야지

[익명(14.46)]

단순 dfs가 아니라 트리/dag dp처럼 탐색 끝내고 뒤에 뭔가 해줘야 할 때 상당히 귀찮아짐