JavaScript 알고리즘 구현 정리[1]

class Stack {
  constructor() {
    this.stack = [];
  }

  push(element) {
    this.stack.push(element); // element를 push한다.
  }

  pop() {
    if (this.stack.length === 0) return false // 0인경우 pop 하는 것은 불가능해요.
    return this.stack.pop(); // pop한 값을 뺀다.
  }
}

class Queue {
  constructor() {
    this.queue = [];
  }

  push(element) {
    this.queue.push(element)
  }

  popleft() {
    // 선입선출의 구조이기 때문에 array 앞부분이 우선적으로 나와야겠죠?
    if (this.queue.length === 0) return false
    return this.queue.shift();
  }
}

class Queue {
  constructor() {
    this.queue = new Map();
    this.front = 0;
    this.back = 0;
}

  push(element) {
    this.queue.set(this.back++, element);
  }

  popleft() {
    if (this.front === this.back) return false; // 비어있음
    const value = this.queue.get(this.front); // 우선 맨 앞의 값을 빼고
    this.queue.delete(this.front++); // 맨 앞 인덱스를 조절한 이후 리턴
    return value;
  }
}

// key : 해당 노드, value : 해당 노드와 연결된 노드 배열
const graph = {
  1: [2],
  2: [1, 3],
  3: [2, 4, 6],
  4: [3, 5],
  5: [4], //
  6: [3, 7],
  7: [6]
};

function dfs() {
  const stack = [];
  const visited = new Set(); // 방문 여부를 판단하기 위함
  let current = 1;
  const trace = []; // 실시간 위치 추적 (어떤 순서로 노드를 확인하는가)
  const result = [1]; // 실질적 탐색 노드 순서 (어떤 순서로 노드를 탐색하는가)

  stack.push(current);
  visited.add(current);

  while (stack.length !== 0) {
    trace.push(current);

    const nextCandidates = graph[current];
    let moved = false; // 이동했는지 체크할 플래그

    for (const nextCandidate of nextCandidates) {
      if (!visited.has(nextCandidate)) {
        visited.add(nextCandidate);
        stack.push(current); // 현재 노드를 다시 스택에 저장 (되돌아오기 위해)
        current = nextCandidate; // 다음으로 이동
        moved = true; // 이동했음
        result.push(nextCandidate);
        break; // 이동했으니까 더 이상 후보 안 본다
      }
    }

    if (!moved) {
      // 이동을 못했으면
      current = stack.pop(); // 스택에서 이전 경로로 backtrack
    }
  }

  return {
    result,
    trace,
  }
}

console.log(dfs()); // result : [1, 2, 3, 4, 5, 6, 7], trace :[1, 2, 3, 4, 5, 4, 3, 6, 7, 6, 3, 2, 1] (stack이 비면 탐색 종료)

function bfs() {
  const queue = []; // 다음 탐색할 노드 후보를 담을 큐
  const visited = new Set(); // 방문한 노드를 기록
  const result = []; // 방문 순서 기록

  let current = 1;
  queue.push(current);
  visited.add(current);

  while (queue.length !== 0) {
    current = queue.shift(); // 가장 먼저 큐에 들어온 노드를 꺼냄
    result.push(current);

    const nextCandidates = graph[current];
    for (const nextCandidate of nextCandidates) {
      if (!visited.has(nextCandidate)) {
        visited.add(nextCandidate);
        queue.push(nextCandidate);
      }
    }
  }
  return result;
}

console.log(bfs()); // [1, 2, 3, 4, 6, 5, 7]