DFS 문제 해결법
DFS에 관해
지금부터 DFS 관련 문제해결 방법에 대해 알아보자.
기본적으로 JS를 한다.
문제해결 순서는 다음과 같다.
- 주어진 문제가 DFS를 필요로 하는지 파악한다.
- DFS 함수를 정의한다.
- DFS 함수를 출력한다.
주어진 문제가 DFS를 필요로 하는지 파악한다.
주어진 문제가 DFS 문제인지 판단하는 것은 매우 간단하다.
문제에서 단순히 한 방향의 iterable한 탐색이 아니고, 순열을 이용한 경우의 수 처럼, 그래프 형태의 탐색이 필요한 경우가 DFS를 적용해야 하는 순간이다.
그 경우, 아무리 발버둥 쳐도 한 방향의 iterable한 탐색으론 절대 풀 수 없다.
DFS 함수를 정의한다.
제일 중요한 과정이다.
우선 DFS를 통해 얻고자 하는 것을 먼저 생각한다.
-
그래프의 깊이: 이 경우 깊이 값(level)을 함수의 parameter로 갖는다. DFS 함수 특성상 재귀함수를 호출할 때마다 level + 1 값을 대입한다. 단, 원하는 깊이에 도달했을 때, 새로운 동작이 필요하므로
level === number
에 대한 조건문을 종료 조건으로 지정한다. 참고로 재귀함수의 호출은 다른 노드로의 이동을 의미한다. -
노드 이동간 바인딩 되는 값: 노드가 이동할 때, 새로 업데이트 되는 값이다. level과 마찬가지로 재귀함수를 호출할 때 새로운 값을 대입한다.
-
바인딩 없이 단순한 방문일 경우, edge의 여부에 따라 노드 이름만 재귀함수에 대입한다.
-
노드 방문했는지에 대한 여부: 다른 좋은 방법도 있겠지만, 내 방법은 다음과 같다.
-
노드 방문 여부를 하나의 배열에 담는다.
-
각 배열의 값은 방문 여부를 나타내는데,
1
은 방문,0
은 방문하지 않은 것이다. -
각 배열의 index 값은 노드를 의미한다. 이게 불편하면 노드 방문 여부를 객체 리터럴 자료구조 파악해도 괜찮다.
-
이 때, 노드를 방문할 때 마다 노드 방문 여부 배열의 값을 변경하는데, 배열에서 대입은 참조에 의한 대입이기 때문에 rest 를 이용해 새로운 포인터를 가진 배열을 만들고 (깊은 복사) 업데이트 후, 재귀함수에 대입한다.
-
const newVisitedArr = [...visitedArr]
newVisitedArr[I] = value
dfs(level, newVisitedArr)
DFS 함수를 출력한다.
-
시작노드가 정해져 있다면, 시작노드만 DFS 함수에 대입한다.
-
정해진 시작노드 없이, 모두 탐색해야 한다면, for문 or iterable method로 완전탐색을 하고, 재 방문을 피해야 하면 방문여부 배열을 잘 활용한다. 이 때 방문여부 배열이 전역적이면 좋은지, 시작 노드에 바인딩 되면 좋은지 고민해 본다.
Author And Source
이 문제에 관하여(DFS 문제 해결법), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cramming/DFS-문제-해결법저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)