[백준] 1260 DFS와 BFS

문제

 

접근법

본 문제는 DFS와 BFS의 기본을 물어보는 문제인 만큼 두 개의 알고리즘을 올바르게 아는 것이 중요하다.

 

그리하여 이 글에서는 접근법을 별도로 기재하는 것이 아닌 DFS & BFS 를 복습하는 차원으로 적어보고자 한다.

 

- DFS

DFS란 깊이우선탐색으로 시작점을 기준으로 아래로 향하는 알고리즘이다.

 

- DFS는 왜 Stack 또는 재귀 ( Recursion ) 을 사용하나요?

 

상단의 그림과 같이 DFS는 현재 위치에서 갈 수 있는 가장 깊은 곳 (= 하단) 으로 이동하는 알고리즘이다.

 

그렇기 때문에, 현재 기점에서 가장 깊은 노드로 이동 하기 위해서는 "호출된 노드의 아래 - 호출된 노드의 아래 .. "

 

와 같은 방식으로 이동 해야 하기에 스택 또는 재귀 함수를 이용하여 보통 해결을 한다.

 

- BFS

BFS란 넓이우선탐색으로 시작점을 기준으로 좌/우로 향하는 알고리즘이다.

- BFS는 왜 Queue를 사용하나요?

 

 

[0] -> [1,2] -> [ 2,3,4 ] -> [ 3,4,5,6] 과 같은 방식으로 이루어지기에 FIFO 방식인 큐를 사용하는 것이 좋다.

 

 

코드

코드는 (1) 스택 + 인접 리스트 을 통해 DFS를 해결 한 경우와 (2) 재귀 + 인접 행렬를 을 통해 해결한 2가지의 경우로 나누어 작성을 합니다!

(1) 의 경우 재귀 호출이 없고, 리스트를 통해 연결 상태를 정리하여 메모리 및 속도가 굉장히 빠른 편이지만,

(2) 의 경우 재귀 및 인접 행렬을 사용하여 메모리 및 속도가 다소 느리게 나오는 모습을 볼 수 있습니다.

 

(1)

function readInputLines() {
  return require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
}

function splitAndParseInt(string) {
  return string.split(" ").map((value) => parseInt(value));
}

function setConnection(graph, start, end) {
  if (start in graph) {
    graph[start].push(end);
  } else {
    graph[start] = [end];
  }
}

function dfs(graph, start, visited) {
  const result = [];
  const stack = [start];
  while (stack.length !== 0) {
    const node = stack.pop();
    if (visited[node]) {
      continue;
    }
    result.push(node);
    visited[node] = true;
    if (!(node in graph)) {
      continue;
    }
    const connected = graph[node].sort((a, b) => b - a);
    for (const v of connected) {
      stack.push(v);
    }
  }
  return result;
}

function bfs(graph, start, visited) {
  const result = [];
  const queue = [start];
  while (queue.length !== 0) {
    const node = queue.shift();
    if (visited[node]) {
      continue;
    }
    result.push(node);
    visited[node] = true;
    if (!(node in graph)) {
      continue;
    }
    const connected = graph[node].sort((a, b) => a - b);
    for (const v of connected) {
      queue.push(v);
    }
  }
  return result;
}

const lines = readInputLines();
const [n, m, v] = splitAndParseInt(lines[0]);

const graph = {};
for (let i = 1; i <= m; ++i) {
  const [v1, v2] = splitAndParseInt(lines[i]);
  setConnection(graph, v1, v2);
  setConnection(graph, v2, v1);
}
const visited = Array(n + 1);
console.log(dfs(graph, v, visited.fill(false)).join(" "));
console.log(bfs(graph, v, visited.fill(false)).join(" "));

(2)

const lines = readInputLines();
const [N, M, V] = splitAndParseInt(lines[0]);
let visited = new Array(N + 1).fill(false);
const map = Array.from(new Array(N + 1), () => new Array(N + 1).fill(0));

for (let i = 1; i <= M; ++i) {
  const [v1, v2] = splitAndParseInt(lines[i]);
  setConnection(map, v1, v2);
}

function readInputLines() {
  return require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
}

function splitAndParseInt(string) {
  return string.split(" ").map((value) => parseInt(value));
}

function setConnection(map, v1, v2) {
  map[v1][v2] = 1;
  map[v2][v1] = 1;
}

let dfsOut = "" + V;
function DFS(V) {
  visited[V] = true;
  for (let i = 1; i <= N; i++) {
    if (map[V][i] === 1 && !visited[i]) {
      dfsOut += " " + i;
      DFS(i);
    }
  }
}

let bfsOut = "" + V;
function BFS(V) {
  visited[V] = true;
  const queue = [V];
  while (queue.length !== 0) {
    const nextV = queue.shift();
    for (let i = 1; i <= N; i++) {
      if (map[nextV][i] === 1 && !visited[i]) {
        visited[i] = true;
        bfsOut += " " + i;
        queue.push(i);
      }
    }
  }
}

DFS(V);
visited = visited.fill(false);
BFS(V);

console.log(dfsOut);
console.log(bfsOut);