DFS 문제 해결법

Cramming An·2022년 3월 31일
0

Code Interview

목록 보기
11/11
post-thumbnail

DFS에 관해

지금부터 DFS 관련 문제해결 방법에 대해 알아보자.
기본적으로 JS를 한다.

문제해결 순서는 다음과 같다.

  1. 주어진 문제가 DFS를 필요로 하는지 파악한다.
  2. DFS 함수를 정의한다.
  3. DFS 함수를 출력한다.

주어진 문제가 DFS를 필요로 하는지 파악한다.

주어진 문제가 DFS 문제인지 판단하는 것은 매우 간단하다.
문제에서 단순히 한 방향의 iterable한 탐색이 아니고, 순열을 이용한 경우의 수 처럼, 그래프 형태의 탐색이 필요한 경우가 DFS를 적용해야 하는 순간이다.
그 경우, 아무리 발버둥 쳐도 한 방향의 iterable한 탐색으론 절대 풀 수 없다.

DFS 함수를 정의한다.

제일 중요한 과정이다.
우선 DFS를 통해 얻고자 하는 것을 먼저 생각한다.

  • 그래프의 깊이: 이 경우 깊이 값(level)을 함수의 parameter로 갖는다. DFS 함수 특성상 재귀함수를 호출할 때마다 level + 1 값을 대입한다. 단, 원하는 깊이에 도달했을 때, 새로운 동작이 필요하므로 level === number에 대한 조건문을 종료 조건으로 지정한다. 참고로 재귀함수의 호출은 다른 노드로의 이동을 의미한다.

  • 노드 이동간 바인딩 되는 값: 노드가 이동할 때, 새로 업데이트 되는 값이다. level과 마찬가지로 재귀함수를 호출할 때 새로운 값을 대입한다.

  • 바인딩 없이 단순한 방문일 경우, edge의 여부에 따라 노드 이름만 재귀함수에 대입한다.

  • 노드 방문했는지에 대한 여부: 다른 좋은 방법도 있겠지만, 내 방법은 다음과 같다.

    1. 노드 방문 여부를 하나의 배열에 담는다.

    2. 각 배열의 값은 방문 여부를 나타내는데, 1은 방문, 0은 방문하지 않은 것이다.

    3. 각 배열의 index 값은 노드를 의미한다. 이게 불편하면 노드 방문 여부를 객체 리터럴 자료구조 파악해도 괜찮다.

    4. 이 때, 노드를 방문할 때 마다 노드 방문 여부 배열의 값을 변경하는데, 배열에서 대입은 참조에 의한 대입이기 때문에 rest 를 이용해 새로운 포인터를 가진 배열을 만들고 (깊은 복사) 업데이트 후, 재귀함수에 대입한다.

const newVisitedArr = [...visitedArr]
newVisitedArr[I] = value
dfs(level, newVisitedArr)

DFS 함수를 출력한다.

  • 시작노드가 정해져 있다면, 시작노드만 DFS 함수에 대입한다.

  • 정해진 시작노드 없이, 모두 탐색해야 한다면, for문 or iterable method로 완전탐색을 하고, 재 방문을 피해야 하면 방문여부 배열을 잘 활용한다. 이 때 방문여부 배열이 전역적이면 좋은지, 시작 노드에 바인딩 되면 좋은지 고민해 본다.

profile
La Dolce Vita🥂

0개의 댓글