질문&답변
DFS 에서 스택을 사용하는 이유
BFS 강의까지 듣고 좀 더 생각을 해보았는데요 Stack은 LIFO, Queue는 FIFO 구조 니까, DFS의 Stack 은 방문 과정에서 스택에 쌓인 노드들이 순차적으로 pop되며, pop된 노드의 다음 깊이의 노드가 새로 쌓이는 형태입니다. 최대 깊이까지 들어간 뒤, 기준이 된 노드와 그 인접 노드들이 모두 pop되면 이제 다음 기준 노드의 인접 노드들이 다시 쌓이고, 다시 나가고의 반복이 이어집니다. (이러면 처음 질문 때 적었던 3. 그래프의 끝까지 깊이 파고들었다가 , 방문하지 않는 노드를 방문하기 위해 나중에 다시 돌아갈 "기준점" 으로 이해할 수 있겠네요) 최근에 쌓인 노드가 먼저 pop되는 특성 덕분에, DFS는 더 깊은 레벨의 노드까지 탐색을 이어갈 수 있는 구조를 갖게 됩니다. → 이런 이유로 DFS는 스택을 사용합니다. 반면 BFS의 Queue 는 인접 노드들이 먼저 탐색되어야 하기 때문에, 한 노드의 인접 리스트를 전부 큐에 넣은 다음, 이전에 미리 쌓아둔 인접 노드들부터 순서대로 탐색을 진행합니다. (그렇기에 POP으로 데이터를 출력하는 DFS와 달리, FIFO 특성인 큐는 이미 인접 노드로 넣은 노드들을 다 방문해야 그 다음 레벨의 노드들을 탐색할 수 있습니다) → 그래서 BFS는 FIFO 구조의 큐를 사용합니다. 이렇게 이해하면 논리의 흐름이 조금 맞을까요? 말로 하려니까 매우 복잡하고 어렵게 표현이 된 것같네요..ㅠㅠㅠ 죄송합니다.. 하지만 아직도 고민인 점은, DFS/BFS에서는 스택이랑 큐를 왜 쓰는지 이해가 되지만 코딩테스트에서 다른 유형(DFS, BFS 외)의 문제들을 풀 때도 여기서는 스택을 써야겠다 혹은 여긴 큐가 맞겠다 같은 판단들을 어떻게 잡는지 궁금합니다. 결국 많이 풀어보면서 감을 익혀야 하는 건지, 아니면 어떤 기준이나 패턴이 있는 건지 알고 싶습니다..!
- 좋아요수
- 1
- 댓글수
- 3
- 조회수
- 209