이번 스터디 주제인 DFS와 BFS에 대해 공부하고 포스팅하려고 한다.
DFS와 BFS는 그래프를 탐색하는 방법을 크게 나눈 것이다.
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것을 말한다.
DFS와 BFS가 무엇이고 문제에서 어떻게 풀어야하는지 알아보자
깊이 우선 탐색(DFS, Depth-First Search)
최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
DFS는 탐색할 때 시작 노드에서 한방향으로 계속 탐색하다가 더이상 갈 수 없을 때
다시 가장 가까운 노드로 돌아와 다시 탐색을 진행하는 방법
예를 들어, 미로를 통과할 때 한방향으로 쭉~ 들어가다가
더이상 길이 없을 때 다시 가장 가까운 갈림길로 돌아가서 다른 방향으로
탐색을 진행하는 것을 예로 들 수 있다.
DFS의 사용, 특징
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
- 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적음
- 찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있음
- 찾은 답이 최단 경로가 된다는 보장이 없음
- 최악의 경우, 모든 경로를 돌고나서 찾으므로, 도달하는데 시간이 오래걸림
DFS를 구현하는데에는 2가지 방법이 있다.
1. 재귀를 이용하는 것
2. 스택(반복문)을 이용하는 것
DFS 구현
1. 재귀를 이용한 DFS(Recursive DFS)
Recursive DFS의 동작 방식
1. 방문 여부를 기록하기 위해 배열 visited를 사용하며, 배열 visited의 값을 false로 초기화한다.
2. 노드를 방문할 때마다 해당 노드의 visited 배열 값을 true로 변경한다.
3. 해당 노드(v)와 연결된 노드 중에 방문하지 않은 노드(node)가 있다면 방문하지 않은
노드(node)를 시작점으로 하여 DFS를 다시 시작한다.
코드로 구현해보면 아래와 같다.
2. 스택을 이용한 DFS(Iterative DFS)
Iterative DFS의 동작 방식
1. 스택에 시작 노드를 push함.
2. 스택에서 노드를 pop하고 해당 노드(v)가 방문하지 않은 노드라면 방문처리를 함
3. 노드(v)와 연결된 노드 중에서 방문하지 않은 노드(node)가 있다면 스택에 push
4. 스택의 길이가 0이 될 때까지 2, 3번의 과정을 반복
아래의 그림을 통해 구현과정을 보면,
아래의 그래프를 DFS로 탐색을 해보자.
1. 시작 노드인 0을 스택에 push한다.
2. 스택에서 0을 pop한 다음 방문 처리를 하고,
0노드의 방문하지 않은 인접 노드 1, 2, 4를 스택에 push한다.
3. 스택의 제일 상위에 있는 4를 pop한 다음 방문처리를 하고,
4 노드의 방문하지 않은 인접 노드 3을 스택에 push한다.
4. 스택에서 3을 pop한 다음 방문처리를 한다.
노드 3의 방문하지 않은 인접 노드는 없기 때문에 무시
5. 스택에서 2를 pop하고 방문 처리를 한다.
노드 2의 방문하지 않은 인접 노드 5를 스택에 push한다.
6. 스택에서 5를 pop하고 방문 처리를 한다.
노드 5의 방문하지 않은 인접 노드 1을 스택에 push한다.
7. 스택에서 1을 pop하고 방문처리를 한다.
노드 1의 방문하지 않은 인접 노드는 없기 때문에 무시.
8. 스택에서 1을 pop한다. 노드1은 이미 방문한 노드이므로 무시.
위의 결과들로 그래프의 탐색 순서는 0 -> 4 -> 3 -> 2 -> 5 -> 1 이 된다.
위의 스택을 이용한 DFS를 코드로 구현해보면 아래와 같다.
Recursive DFS vs Iteractive DFS
출력된 결과를 보면 Recursive DFS는 사전식 순서로 방문하여 0 1 6 2 3 4 5 가 나왔다.
하지만 Iteractive DFS는 역순으로 방문을 하여 큰 수부터 방문을 하였다.
왜 이런걸까??
Iteractive DFS는 스택으로 구현하다보니까 가장 마지막에 push된 노드부터 꺼내기 때문에
인접노드를 사전식 순서로 스택에 넣다 보면, 가장 마지막에 push된 큰수부터 방문하기 때문이다.
하지만 결국은 모든 노드의 방문을 한 것이기 때문에 잘못된 결과는 아니다.
가끔 코딩 테스트에서 낮은 순서부터 처리하도록 명시된 경우에는 이를 신경써주어야 한다.
Iteractive DFS의 문제점
재귀를 이용한 DFS(Recursive DFS)로 문제를 해결하다보면 시간초과가 발생할 때가 있다.
이를 자바스크립트로 해결하기 위해서는 스택을 이용한 DFS(Iteractive DFS)를 이용해야한다.
만약, 문제에서 리프노드에서 어떤 연산을해서 부모 노드로 결과값을 전달해야하는데
Recursive DFS는 해당 연산을 모든 탐색이 끝나는 지점에서 수행할 수 있다.
더이상 탐색할 노드가 없어서 탐색이 끝나면 Recursive DFS는 부모로 돌아오는 로직이 존재하지만,
Iteractive DFS는 존재하지 않는다. 이유는 현재 노드가 스택에서 pop되기 때문에
부모로 돌아오는 것이 아니라 제일 상위에 있는 부모의 자식노드로 넘어가게 된다.
따라서, Iteractive DFS를 Recursive DFS와 같이 만들어주어야 한다.
Iteractive DFS 개선하기
위에서 나온 Iteractive DFS의 문제점을 개선해보자
부모노드를 추적하고 부모노드로 돌아가는 로직을 위해 스택에서 pop하고
다시 push를 해주는 작업을 한다.
하지만 이때 무한루프에 빠질수 있기에 pop과 push사이에 조건을 넣어주어야한다.
55~57번줄의 코드가 그 조건이 된다.
그러고 방문하지 않았던 노드라면 cur은 부모 노드가 되어 다음 노드를 계속 탐색한다.
위의 개선된 Iteractive DFS의 동작과정을 알아봐보자
1. 시작 노드인 0을 스택에 push한다. 이때 0은 루트노드(부모가 없는 노드)이므로
부모노드는 -1라는 존재하지않는 수를 넣어준다.
2. 스택에서 [0,-1]을 pop하고 방문한 노드인지 확인한다.
노드 0은 방문하지 않은 노드이므로 다시 스택에 push하고 방문처리를 한다.
0노드의 방문하지 않은 인접 노드 1, 2, 4를 부모노드인 0과 함께
[1,0], [2,0], [4,0] 형태로 스택에 push한다.
3. 스택의 제일 상위에 있는 [4,0]을 pop하고 방문한 노드인지 체크한다.
노드 4는 방문하지 않은 노드이므로 다시 스택에 push하고 방문처리를 한다.
4노드의 방문하지 않은 인접 노드 3을 부모노드인 4와 함께 [3,4]형태로 스택에 push
4. 스택에서 [3,4]를 pop하고 방문한 노드인지 체크한다.
노드 3은 방문하지 않은 노드이므로 다시 스택에 push하고 방문처리를 한다.
노드 3의 인접 노드 중에 방문하지 않은 노드가 없으므로 다음과정 무시
5. 스택에서 [3,4]를 pop한다.
노드 3은 방문한 노드이므로 다음 과정은 무시하고 다음 반복으로 넘어감.
6. 스택에서 [4,0]을 pop한다.
노드 4는 방문한 노드이므로 다음 과정은 무시하고 다음 반복으로 넘어감.
7. 스택에서 [2,0]을 pop하고 방문한 노드인지 확인한다.
노드 2는 방문하지 않은 노드이므로 다시 스택에 push하고 방문처리를 한다.
2 노드의 방문하지 않은 인접 노드 5를 부모노드인 2와 함께 [5,2]형태로 스택에 push
8. 스택에서 [5,2]을 pop하고 방문한 노드인지 확인한다.
노드 5는 방문하지 않은 노드이므로 다시 스택에 push하고 방문처리를 한다.
5 노드의 방문하지 않은 인접노드 1을 부모노드인 5와 함께 [1,5]형태로 스택에 push
9. 스택에서 [1,5]을 pop하고 방문한 노드인지 확인한다.
노드 1은 방문하지 않은 노드이므로 다시 스택에 push하고 방문처리를 한다.
노드 1의 방문하지 않은 노드가 없으므로 다음과정은 무시
10. 나머지 노드들은 모두 방문한 노드이므로 스택에서 하나씩 pop되어 반복이 종료
솔직히... 이해하기가 좀 어려웠다.
뭐 이렇게 스택에서 빠진다는건 알겠는데 이걸 문제에서
정확히 어떻게 활용해야할지는 문제를 많이 풀어보면서 익혀야할 것 같다.
다음 포스팅 BFS까지 공부하고 포스팅해보고
스터디에서 정해놓은 DFS, BFS 문제들을 풀어봐야겠다.
