[알고리즘] BFS, DFS

BFS

- 모든 노드를 너비를 우선으로 방문하기 위한 알고리즘

- 모든 간선의 길이가 동일한 상황에서 두 지점 사이의 거리를 찾는 문제는 BFS로 해결 가능

- 인접 리스트, 인접 행렬로 풀이 가능

 

BFS 연결 그래프 순회 (인접 리스트 방식)

const adj = new Array(10).fill(0).map(() => []);
const vis = new Array(10).fill(false);

function bfs() {
  const q = [];

  // 시작 노드를 큐에 넣고 방문 처리
  q.push(1);
  vis[1] = true;

  // 큐가 비어있지 않은 동안 반복
  while (q.length > 0) {
    // 큐의 맨 앞 노드를 가져오기
    const cur = q.shift();

    // 현재 노드 출력
    console.log(cur);

    // 인접 노드 순회
    for (const nxt of adj[cur]) {
      // 이미 방문한 노드라면 건너뛰기
      if (vis[nxt]) continue;

      // 방문하지 않은 노드라면 큐에 추가하고 방문 처리
      q.push(nxt);
      vis[nxt] = true;
    }
  }
}

 

연결 그래프에서 1번 정점까지의 거리

const adj = new Array(10).fill(0).map(() => []);
const dist = new Array(10).fill(-1);

function bfs() {
  const q = [];

  // 1번 노드부터 탐색 시작
  q.push(1);
  dist[1] = 0; // 시작 노드의 거리를 0으로 설정

  // 큐가 비어 있지 않은 동안 반복
  while (q.length > 0) {
    const cur = q.shift(); // 현재 노드

    // 인접한 노드 순회
    for (const nxt of adj[cur]) {
      // 이미 방문한 노드(거리가 -1이 아닌 경우)는 건너뛰기
      if (dist[nxt] !== -1) continue;

      // 큐에 다음 노드를 추가
      q.push(nxt);
      
      // 거리 갱신
      dist[nxt] = dist[cur] + 1;
    }
  }
}

 

연결 그래프가 아닐 때 순회

const adj = new Array(10).fill(0).map(() => []);
const vis = new Array(10).fill(false);
const v = 9; // 정점의 수

function bfs() {
  const q = [];

  // 모든 정점을 순회, 아직 방문하지 않은 정점에서 BFS 시작
  for (let i = 1; i <= v; i++) {
    // 이미 방문한 정점이면 건너뜁니다.
    if (vis[i]) continue;

    // 새로운 시작점을 큐에 넣고 방문 처리
    q.push(i);
    vis[i] = true;

    // 큐가 비어 있지 않은 동안 반복
    while (q.length > 0) {
      const cur = q.shift();

      // 현재 노드 출력
      console.log(cur);

      // 인접한 노드들을 순회
      for (const nxt of adj[cur]) {
        // 이미 방문한 노드라면 건너뜁니다.
        if (vis[nxt]) {
          continue;
        }

        // 방문하지 않은 노드라면 큐에 추가하고 방문 처리
        q.push(nxt);
        vis[nxt] = true;
      }
    }
  }
}

DFS

-  모든 정점을 깊이 우선으로 순회할 수 있는 알고리즘

- 재귀를 이용해서 풀이 가능 → 재귀 특성상 LIFO로 호출되기때문에 stack과 같다는 특성이 있음 (호출 스택 이용)

- 스택 영역의 메모리 제한을 1MB, 10MB로 작게 제한을 걸어두면 재귀대신 stack을 사용하기 => 깊이가 깊어지면 스택메모리가 버티지 못함

 

DFS 스택 방식

const adj = new Array(10).fill(0).map(() => []);
const vis = new Array(10).fill(false);

function dfs() {
  // 스택을 위한 배열
  const s = [];

  // 시작 노드를 스택에 넣고 방문 처리
  s.push(1);
  vis[1] = true;

  // 스택이 비어있지 않은 동안 반복
  while (s.length > 0) {
    // 스택의 마지막 노드를 가져오기
    const cur = s.pop();

    // 현재 노드 출력
    console.log(cur);

    // 인접한 노드들을 순회
    for (const nxt of adj[cur]) {
      // 이미 방문한 노드라면 건너뛰기
      if (vis[nxt]) continue;

      // 방문하지 않은 노드라면 스택에 추가하고 방문 처리
      s.push(nxt);
      vis[nxt] = true;
    }
  }
}

 

DFS 재귀 방식

const adj = new Array(10).fill(0).map(() => []);
const vis = new Array(10).fill(false);

function dfs(cur) {
  // 현재 노드를 방문 처리
  vis[cur] = true;

  // 현재 노드 출력
  console.log(cur);

  // 인접한 노드들을 순회
  for (const nxt of adj[cur]) {
    // 이미 방문한 노드라면 건너뛰기
    if (vis[nxt]) continue;

    // 방문하지 않은 노드라면 재귀적으로 DFS 호출
    dfs(nxt);
  }
}

 

재귀 방식과 비재귀 방식의 DFS 방문순서 차이

- 비재귀 방식으로 구현 시 스택에 값을 넣을때 노드를 방문처리하면 아래와같이 방문순서가 달라짐!

- 따라서 전통적인 DFS 방식으로 방문순서가 정해지길 원한다면 스택에서 값을 뽑을때 방문처리를 해줘야함 (아래코드 참고)

재귀와 스택으로 구현한 DFS 방문순서 차이

const adj = new Array(10).fill(0).map(() => []);
const vis = new Array(10).fill(false);

function dfs() {
  const s = [];
  s.push(1);

  while (s.length > 0) {
    const cur = s.pop();

    // 꺼낸 후 방문 여부를 확인하고, 방문하지 않았다면 탐색을 계속
    if (vis[cur]) continue;
    vis[cur] = true;
    
    console.log(cur);

    // 인접 노드를 스택에 추가
    for (const nxt of adj[cur]) {
      if(vis[nxt]) continue;
      s.push(nxt);
    }
  }
}