DFS 이해 정리

생각정리

puy0 2023. 4. 27. 05:41

DFS/BFS 문제를 만났다

DFS 를 할때 이미 메모리에 올라간 노드는 다시 올리지 않는다는 설명이 있었다

하지만 그렇게 될경우 깊이 탐색을 할수 없다

한번에 2개의 인접 노드가 메모리에 올라가게 되고

먼저 올라간 노드는 나중에 올라간 노드가 처리되기 전까지 메모리에 남아있게 된다

나중에 올라간 노드가 다른 인접노드를 메모리에 올릴때

순환하는 노드가 있게 된다면 중복된 노드는 메모리에 올리지 못하고

헤당노드는 탐색을 할수 없다

먼저 처리할 메모리가 다 정리 되고 난뒤 중북 노드를 처리하게 되고

이 노드는 먼저 처리 되었어야 깊이탐색의 의미를 충족 할수 있게 된다

이러한 문제는 인접한 노드를 언제 메모리에 올릴것인지에 어떻게 생각하냐에 따라 달라진다

리스트의 개념은 정해져있지만 어떻게 사용하는지는 알고리즘 문제마다 다르다

그처럼 DFS 알고리즘또한 언제 메모리에 올릴것이냐는 그래프의 인접노드의 모양에 따라 달라질수 있는것이다

글로 풀어쓰면 햇갈리니 이런 생각을 하게된 강의랑크를 걸었다

엔지니어 대한민국

www.youtube.com

얼마없는 시각적 알고리즘 강의 인데 알기 쉽게 설명해준다

해당영상에서의 DFS 설명은 해당 그래프에서 메모리에 올리는 때가 올바를지 몰라도

8:00 이후 설명

에서 인덱스를 확인 할때 주의 해야할점을 설명해주는대 처음의 강의와 다른 방향으로 설명을 해주신다

DFS/BFS가 어떤원리인지 케치만 하고

문제를 풀때는 유연하게 그 문제에 대응가능 하도록할 필요가 있다

+ 이미 사용한 데이터(방문한 노드)는 메모리에 올리지 않을때 DFS가 불가능하다는 생각은

방문, 탐색에 필요한 특정 규칙을 어떻게 정의 하는지에 따라 다르며

불가능한 가정을 바탕으로 풀어내려 했기 때문에 이러한 의문이 있었다

많은 문제를 풀어보며 해법을 익히는것이 이 의문의 해답 이었다