알고리즘 수업 - 깊이 우선 탐색 1

• https://www.acmicpc.net/problem/24479

오늘의 학습 키워드

DFS

• 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법이다
• 완전탐색을 수행하기 위해 사용할 수 있는 가장 간단한 방법 중 하나이다
• 스택(stack) 자료구조를 사용한다

DFS 기본 동작 방식

1. 시작 노드를 스택에 넣고 방문 처리한다
2. 스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다

• 있다면, 방문하지 않은 인접 노드를 스택에 삽입하고 방문 처리한다
• 없다면, 현재 노드(스택에 마지막으로 들어온 노드)를 스택에서 추출한다

3. 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다

DFS 사용 예시

• 더 짧은 코드로 간결히 구현해야 하는 경우
• 큐 라이브러리를 사용할 수 없는 경우
• 트리의 순회, 점화식 구현 등 DFS(재귀 구조)에 특화된 문제인 경우
• 트리에서 최단 거리 탐색을 구하는 경우

문제 해결 방법

• 인접 정점은 오름차순으로 방문한다
• 무방향 그래프이기 때문에, 그래프를 그릴 때 정점 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"));