[JS/코테] 백준 1260 DFS와 BFS

DFS와 BFS

문제 및 조건 설명: https://www.acmicpc.net/problem/1260

알고리즘 설계

💡idea.

• 상세 구현 방법은 다 다르지만, BFS, DFS 구현의 스타트는 각각 Stack, Queue를 기준으로 반복한다는 것이다.
  방문할 것들이 저장되고, 꺼내서 검사한다.
• stack을 사용하는 DFS 구현을 Iterative DFS 라고 한다.
• 입력값은 인접리스트로 받는다. 이 때, 번호가 작은 정점을 우선으로 하기 위해 오름차순으로 정렬한다. 

🎲step.

입력값은 인접리스트로 받고, 오름차순 정렬한다. 양방향 그래프이므로 두 번 push 해준다.

출력값은 배열을 문자열로 바꾸어서 숫자만 출력한다.

let input = []; // 전체 입력값을 넣어줄 리스트 생성
let g = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [n, m, v] = input[0].split(" ").map(Number);

  g = Array.from({ length: n + 1 }, () => []);

  for (let i = 1; i <= m; i++) {
    const [a, b] = input[i].split(" ").map(Number);
    g[a].push(b);
    g[b].push(a);
  }
  // 오름차순 정렬
  g.forEach((adjList) => adjList.sort((a, b) => a - b));

  console.log(dfs(n, g, v).join(" "));
  console.log(bfs(n, g, v).join(" "));
});

기본 Iterative DFS는 이 포스팅을 참고했다.

    * 부모 노드는 추가할 필요없지만, 다른 응용 문제를 위해 연습 구현했다.

변형한 부분은, 번호가 작은 정점을 우선 방문하기 위해 역순으로 stack에 추가해준 부분이다.

const dfs = (n, g, start) => {
  let result = [];
  let visited = Array(n + 1).fill(false);
  const stack = [start];

  while (stack.length) {
    const cur = stack.pop();

    if (!visited[cur]) {
      visited[cur] = true;
      result.push(cur);

      // 큰 숫자부터 스택에 넣어야 pop할 때 작은 숫자부터 나오도록 역순 정렬
      for (let i = g[cur].length - 1; i >= 0; i--) {
        const node = g[cur][i];
        if (!visited[node]) stack.push(node);
      }
    }
  }

  return result;
};

BFS도 반복문과 queue를 사용해서 구현한다.

queue에 추가(push)할 때는 이미 오름차순 정렬되어 있으므로 순차 반복해준다. queue 이므로 pop대신 shift 메서드를 사용한다.

const bfs = (n, g, start) => {
  let result = [];
  let visited = Array(n + 1).fill(false);
  const queue = [start];
  visited[start] = true;

  while (queue.length) {
    const cur = queue.shift();
    result.push(cur);

    // 작은 숫자부터 큐에 넣기 위해 오름차순 정렬
    for (const node of g[cur]) {
      if (!visited[node]) {
        visited[node] = true;
        queue.push(node);
      }
    }
  }

  return result;
};

알고리즘 구현

위의 모든 구현을 합친 정답 코드는 아래와 같다. 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const dfs = (n, g, start) => {
  let result = [];
  let visited = Array(n + 1).fill(false);
  const stack = [start];

  while (stack.length) {
    const cur = stack.pop();

    if (!visited[cur]) {
      visited[cur] = true;
      result.push(cur);

      for (let i = g[cur].length - 1; i >= 0; i--) {
        const node = g[cur][i];
        if (!visited[node]) stack.push(node);
      }
    }
  }

  return result;
};

const bfs = (n, g, start) => {
  let result = [];
  let visited = Array(n + 1).fill(false);
  const queue = [start];
  visited[start] = true;

  while (queue.length) {
    const cur = queue.shift();
    result.push(cur);

    for (const node of g[cur]) {
      if (!visited[node]) {
        visited[node] = true;
        queue.push(node);
      }
    }
  }

  return result;
};

let input = [];
let g = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [n, m, v] = input[0].split(" ").map(Number);

  g = Array.from({ length: n + 1 }, () => []);

  for (let i = 1; i <= m; i++) {
    const [a, b] = input[i].split(" ").map(Number);
    g[a].push(b);
    g[b].push(a);
  }
  g.forEach((adjList) => adjList.sort((a, b) => a - b));

  console.log(dfs(n, g, v).join(" "));
  console.log(bfs(n, g, v).join(" "));
});

나다어

• 정리하자면, 구현을 위해서는 ①원본 그래프(input값) ②Stack/Queue ③방문확인배열 이 필요하다.
• 입력값을 정리하는 것 또한 중요하다. 오늘 문제에서는 인접 리스트로, 오름차순 정렬로 그래프를 정리했다.
• 구조 분해 할당은 배열을 펼치고 반복할 필요 없이 유용하게 쓰인다.

✔️이차원 배열 선언

  let numArr = new Array(n + 1).fill([]);
  let numArr = new Array(n + 1).fill().map(() => []);

첫 번째와 같이 선언하면, 이차원 배열 내부 원소는 모두 같은 참조를 가지게 되어 특정 인덱스에 값을 추가하는 것이 불가능하고 모든 인덱스에 값이 추가된다. 각 인덱스에 서로 다른 배열을 넣어주기 위해서는 반복문을 이용해야 한다. 

let numArr = Array.from({ length: n + 1 }, () => []);

fill 메서드는 배열을 undefined로 채운 후, map을 통해 요소를 추가하도록 동작한다. 그러나 Array.from 메서드를 사용하면 배열을 생성하면서 각 요소에 콜백 함수가 바로 실행되기 때문에 조-금 더 효율적이라고 볼 수 있다. 

---

참고: 

https://chamdom.blog/dfs-using-js/

[알고리즘] JavaScript로 구현하는 DFS