인프런 커뮤니티 질문&답변
작성한 질문수
DFS 에서 스택을 사용하는 이유
작성
·
16
0
안녕하세요, 현재 DFS 관련하여 내용을 수강하고 있습니다. (39강. DFS & BFS)
깊이 탐색인 알고리즘인 DFS를 처음엔 재귀로 접근하셨다가 RecursionError의 이유로 스택을 사용하셨는데요, 스택을 생각하게 된 생각의 흐름(?)을 잡아보고싶어 질문을 드리게되었습니다.
(나중에 코테 연습 때 대비가 될까하여 더 고민을 해보는 것인데, 시간대비 효율이 나지않는다면 말씀해주세요 ㅎㅎ)
일단 제가 이해한 흐름은 여기까지입니다.
DFS는 깊이 우선 탐색
깊이 파고들었다가 다시 나오고 반복
그래프의 끝까지 깊이 파고들었다가, 방문하지 않는 노드를 방문하기 위해 나중에 다시 돌아갈 "기준점"이 필요하게 될 것임
그렇다면 이전에 어디까지 방문했는지 기록을 해놓아야함
어떻게 해야 기록을 더 효율적으로 할 수 있을까?
하지만 여기서 스택을 사용해야겠다고 생각이 들게 되는 이유를 찾고 싶습니다 ㅎㅎ
알고리즘을 잘하시는 분들 보시면 이런 부분은 큐를 써야겠고, 스택을 써야겠다 라고 바로 생각을 하시는데, 저로서는 왜 이게 바로 스택을 써야한다고 생각이 드는지 이해가 되질 않아서요
혹여 이전에 강의때 설명하신 부분이라면 죄송합니다..ㅎㅎ
답변 2
0
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 외)의 문제들을 풀 때도 여기서는 스택을 써야겠다 혹은 여긴 큐가 맞겠다 같은 판단들을 어떻게 잡는지 궁금합니다.
결국 많이 풀어보면서 감을 익혀야 하는 건지, 아니면 어떤 기준이나 패턴이 있는 건지 알고 싶습니다..!
0
안녕하세요, 인프런 AI 인턴입니다. 깡패 햄스터님.
깊이 우선 탐색(DFS)에서 왜 스택을 사용하는지에 대한 질문을 주셨네요. 사실 DFS는 깊이를 우선적으로 탐색하기 때문에, “가장 마지막에 추가된 노드”부터 탐색을 이어가는 특징이 있습니다. 이는 자연스럽게 스택의 LIFO(Last In First Out) 특성과 맞아 떨어집니다. 아래에서 이해를 도울 수 있도록 주요 이유를 설명드리겠습니다.
DFS에서 스택을 사용하는 이유
DFS의 탐색 방향:
- DFS는 말 그대로 깊이 우선 탐색입니다. 즉, 한 길로 깊이 들어가다가 더 이상 진행할 수 없을 때 돌아오게 됩니다. 이때, 돌아오는 과정을 스택이 지원합니다.
- DFS는 말 그대로 깊이 우선 탐색입니다. 즉, 한 길로 깊이 들어가다가 더 이상 진행할 수 없을 때 돌아오게 됩니다. 이때, 돌아오는 과정을 스택이 지원합니다.
LIFO 구조:
- 스택은 자료를 넣었다가(LIFO: Last In First Out) 마지막에 넣은 것이 가장 먼저 나오는 구조입니다. 이는 DFS 탐색이 더 깊이 들어갔다가 다시 돌아오는 과정에 부합합니다.
- 스택은 자료를 넣었다가(LIFO: Last In First Out) 마지막에 넣은 것이 가장 먼저 나오는 구조입니다. 이는 DFS 탐색이 더 깊이 들어갔다가 다시 돌아오는 과정에 부합합니다.
이미지로 이해하기:
- 스택을 이용한 DFS 이해하기에서는 DFS 과정에서 스택이 자료를 어떻게 쌓고 제거하는지 시각적으로 설명합니다.
- 스택을 이용한 DFS 이해하기에서는 DFS 과정에서 스택이 자료를 어떻게 쌓고 제거하는지 시각적으로 설명합니다.
재귀와의 관계:
- DFS를 재귀적으로 구현하면 시스템의 호출 스택(call stack)을 이용하게 됩니다. 하지만 재귀로 인해 발생할 수 있는
RecursionError를 피하고자 명시적 스택(명시적으로 구현한 스택)을 사용하면 보다 안전하게 구현할 수 있습니다.
- DFS를 재귀적으로 구현하면 시스템의 호출 스택(call stack)을 이용하게 됩니다. 하지만 재귀로 인해 발생할 수 있는
효율적인 방문 관리:
- 스택을 사용하여 이전에 방문한 상태를 저장하고 쉽게 돌아갈 수 있습니다. 즉, “방문 처리 후 탐색을 끝내고 돌아갈 지점”을 스택으로 관리하는 것이죠.
- 스택을 사용하여 이전에 방문한 상태를 저장하고 쉽게 돌아갈 수 있습니다. 즉, “방문 처리 후 탐색을 끝내고 돌아갈 지점”을 스택으로 관리하는 것이죠.
고민의 시간을 줄이고자 한 가지 팁을 드리자면, DFS 혹은 깊이 우선으로 “한 길로 끝까지 갔던” 방문 순서를 효율적으로 관리해야 할 때는 스택을 고려하시면 됩니다. 반대로, BFS처럼 “순차적으로 넓혀 가면서 오는 순서대로 처리할 때”는 큐를 활용하시면 좋습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.