[JS] DFS

이번에도 알고리즘 문제를 풀다보니 공부하게 된 지식이 있다.
바로 bfs, dfs이다. 오늘 이 포스트에서는 dfs를 주로 다뤄보겠다.

dfs란?

Depth-First-Search
dfs란 깊이 우선 탐색이다. 쉽게 말하면 말 그대로 깊게 있는 노드(사진 상 맨 아래에 위치한 노드)까지 다 탐색한 후, 옆으로 이동하며 하나씩 불러오는 것이다.
사진을 보면 A-B-D-E-F까지 A를 중심으로 왼쪽 편에 있는 노드들을 제일 아래까지 다 읽은 후, C-G-H-I-J 순으로 오른쪽 아래로 점점 이동하는 것을 볼 수 있다.

간단하게 코드로 구현해본다면?

const graph={
    A:["B","C"],
    B:["A","C","D"],
    C:["A","B","D"],
    D:["B","C"]
};

let visited = [];
let visitedNode = [];
function dfs(start){
    if(!visitedNode.includes(start)){
        visited[start]=true;
        visitedNode.push(start);
    }
    for(let curNode of graph[start]){
        if(!visited[curNode]){
            dfs(curNode);
        }
    }
}
dfs("A");
console.log(visitedNode);

스택, 트리 등을 이용한 수많은 방법이 있지만, 스택 같은 경우 시간 복잡도가 높을 때가 있어 나에게는 이 "재귀"를 이용한 방법이 가장 이해가 잘 되었다.
그래프 객체로 각 노드에 연결된 노드들을 넣어주고, 방문하면 방문했다는 것을 확인하기 위해 배열에 넣어준다. 이후 각 노드들을 돌며 방문한 노드는 안지나가게 !visited로 구분해서 for문을 돌게 한다.

그래서 이 개념을 왜 공부했는가?

백준 백트래킹 N과M1
백준 백트래킹 N과M2
백준 백트래킹 N과M3
백준 백트래킹 N과M4

위의 네 문제는 순열과 조합 개념을 사용한 dfs 기본 문제들이다. dfs를 모르고 풀게 되니, 막막하고 시간 초과를 무수히 겪었다.
네문제 모두 코드가 비슷하고 활용만 살짝 하면 됐기 때문에 1번 문제로 연습하고 2~4번 문제를 아예 처음부터 코드를 작성하며 연습했다.

지금 보게될 풀이는 N과M1 풀이이다.

let fs = require("fs");
let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map((element) => Number(element));
  
const dfs = (cnt) => {
  if (cnt === M) { // M개 만큼 뽑았을 때 결과 출력
    console.log(array.join(" "));
    return;
  }
  for (let i = 1; i <= N; i++) {
    if (!visited[i]) {
      visited[i] = true;
      array[cnt] = i;
      dfs(cnt + 1);
      visited[i] = false;
    }
  }
};

const N = input[0];
const M = input[1];
const visited = new Array(N + 1).fill(false);
const array = [];
dfs(0);

여기서 좀 더 개선한다면 console을 여러번 찍는 것이 아닌 result라는 문자열을 선언한 후

result+=`${array.join(" ")}\n`

과 같이 했다면 조금 더 나은 코드가 될 수 있다.
하지만 $가 어색하시다면 일단은 console로라도 ㅎㅎ..

오늘 학습한 내용으로 내일은 N-Queen을 풀어볼 예정이다.

결론
dfs는 처음에는 어렵지만 하다보면 할만하고 활용도가 높은 알고리즘이다.
공부해두자!