DFS 알고리즘을 어떻게 사용하는지와 언제 사용 가능한지를 정리하는 글이다.

DFS

재귀함수를 알고 있다는 가정으로 시작한다.

DFS는 깊이 우선 탐색이다. 밑에 그림을 보고 이해하는게 빠르다.

위와 같은 이진트리가 있다면 DFS는 깊이를 먼저 탐색하는 방법이다.
위 그림에서 1번 > 2번 > 4번 > 5번 > 3번 > 6번 > 7번 순으로 같은 Level이 아닌 깊이에 왼쪽 값부터 탐색해 나가는 방식이다.

예제 1)

모든 경우의 수를 적용해보고 싶은 경우 DFS를 적용하면 좋다.

문제

두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며, 그 크기는 1,000,000
이하입니다.

▣ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

▣ 입력예제 1
6
1 3 5 6 7 10

▣ 출력예제 1
YES

위 문제는 하나의 부분집합의 배열을 만들고 그 합과 나머지 배열의 합이 같은지를 모두 비교하다가 모두 끝까지 배열을 탐색했을때 같은 경우가 나오면 YES를 출력하고 그곳에서 멈춰주면 된다.

이 문제를 풀기 위해서는 각각의 원소의 사용여부의 경우의수를 모두 판단해야 하기 때문에 DFS로 푸는게 편하다

function solution(arr) {
  let answer = 'NO';
  let n = arr.length;
  let total = arr.reduce((a, b) => a + b, 0);
  function DFS(l, sum) {
    if (l === n) {
      if (total - sum === sum) {
        return 'YES';
      }
    } else {
      DFS(l + 1, sum + arr[l]);
      DFS(l + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}

solution([1, 3, 5, 6, 7, 10]);

예제 2)

미로 찾기 문제의 경우도 DFS를 이용해서 구할 수 있다.
하지만 미로 찾기 문제의 경우도 제일 짧은 경로를 찾는게 아닌 모든 경로를 찾는 경우의 수를 구할 때 사용하면 좋다.

문제

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격
자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격
자판의 움직임은 상하좌우로만 움직인다.

아이디어

이 문제는 모든 경로를 탐색하는 문제이기 때문에 DFS로 루프를 돌면서 위 아래 왼 오른쪽 모든 경로의 경우의 수를 판단하면 된다.
그리고 한번 방문한 지역은 1로 바꿔줘서 반복해서 방문하지 않도록 하는게 중요하다.

function solution(arr) {
  let answer = 0;
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];
  
  function DFS(x, y) {
    if (x === 6 && y === 6) {
      answer += 1;
    } else {
      for (let i = 0; i < 4; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];
        
        if (nx >= 0 && ny >= 0 && arr[nx][ny] === 0) {
          arr[nx][ny] = 1;
          DFS(nx, ny);
          arr[nx][ny] = 0;
        }
      }
    }
}