알고리즘 수업 - 깊이 우선 탐색 1 (opens in a new tab)

문제 해결 방법

인접 정점은 오름차순으로 방문한다
무방향 그래프이기 때문에, 그래프를 그릴 때 정점 u와 정점 v는 양방향임을 고려한다
DFS를 활용해 문제를 해결한다
1. 시작 노드를 스택에 넣고 방문 처리한다
2. 스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다

코드

// input
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [[N, M, R], ...edges] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((line) => line.split(" ").map(Number));
 
// G (graph)
const G = Array.from(new Array(N + 1), () => []);
 
edges.map(([u, v]) => {
  G[u].push(v);
  G[v].push(u);
});
 
G.map((node) => node.sort((a, b) => a - b));
 
// DFS
const visited = Array(N + 1).fill(0);
let visitOrder = 1;
 
function dfs(node) {
  if (!visited[node]) {
    visited[node] = visitOrder;
    visitOrder++;
 
    G[node].forEach((next) => dfs(next));
  }
}
 
dfs(R);
 
// output
console.log(visited.slice(1).join("\n"));

43238 01 Understand Dfs